原題

http://poj.org/problem?id=1742

題目大意

給出硬幣面額及每種硬幣的個數，求從1到m能湊出面額的個數。

題目分析

多重背包模板題,這里講一下用一維dp來解這道題.與完全背包和01背包不同的是,這里dp定義比較特殊,單獨的dp[i]沒有意義的.所以先直接講一下dp更新過程,首先外循環i=1→n遍歷硬幣,內循環從j=0→m遍歷面額,然后這里dp[j]的意義是,硬幣湊成j面額時第i種還剩下幾個,所以說這個dp離開外循環i=1→n時沒意義的.這里dp數組初始化為-1,-1表示不能湊成該面額,然后dp[0]=0.設定完這些就可以開始更新dp了,dp[j]需要更新的情況有(1)假設現在是第i個外循環,如果dp[j]>=0的,表示在用i-1硬幣時能湊到這個面額(不管它剩下多少),直接令dp[j]=c[i],因為用前i-1種硬幣已經能夠湊到這個面額了,那么第i種硬幣可以不需要用,即剩下c[i].(2)如果dp[j]等于-1,而dp[j-v[i]]>0,表示在用第i種硬幣進行更新時,能湊到j-v[i]的面額并且還有剩下,則可以從j-v[i]面額用一個第i種硬幣湊到j面額,此時有dp[j]=dp[j-v[i]]-1.(注意不要j-v[i]越界).最后答案只需要掃一遍dp數組看有幾個是不為-1的輸出即可.

代碼

1 #include <cstdio> 2 #include <cmath> 3 #include <iostream> 4 #include <cstring> 5 #include <algorithm> 6 #include <vector> 7 #include <string> 8 #include <utility> 9 #include <queue> 10 #include <stack> 11 const int INF=0x3f3f3f3f; 12 using namespace std; 13 14 15 int dp[100001]; 16 int v[101]; 17 int c[101]; 18 19 int main() 20 { 21 int n,m; 22 while(cin>>n>>m&&(m||n)) 23 { 24 for(int i=1;i<=n;i++) cin>>v[i]; 25 for(int i=1;i<=n;i++) cin>>c[i]; 26 memset(dp,-1,sizeof(dp)); 27 dp[0]=0; 28 for(int i=1;i<=n;i++) 29 for(int j=0;j<=m;j++) 30 { 31 if(dp[j]>=0) dp[j]=c[i]; 32 else if(j>=v[i]&&dp[j-v[i]]>0) dp[j]=dp[j-v[i]]-1; 33 } 34 int ans=0; 35 for(int i=1;i<=m;i++) if(dp[i]>=0) ans++; 36 cout<<ans<<endl; 37 memset(v,0,sizeof(v)); 38 memset(c,0,sizeof(c)); 39 } 40 return 0; 41 }

?

轉載于:https://www.cnblogs.com/VBEL/p/10433218.html

總結

以上是生活随笔為你收集整理的Coins POJ - 1742(题解)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。