題目描述： 題目鏈接：https://vjudge.net/PRoblem/POJ-1742 這道題的意思是給你一定種類（n）的不同價值的硬幣，每種價值的硬幣給定一定的數目。問你使用這些硬幣可以組合出多少種不大于m的價格。 題目分析： 這道題是一道動態規劃的題，動態規劃是一道至今也讓我很迷的題目，不是很懂他的遞推公式是怎么推出來的，推出來的這個公式為什么合理。這個題目前是在看一位學長的代碼的情況下一點點模仿出來的。 既然給定了i和n，那么就可以分解為子問題，用前J(j<=i)個硬幣可以組合出多少種價格，將問題分解為子問題。 給出代碼：
#include <iostream>#include <algorithm>#include <iomanip>#include <map>#include <cstdio>#include <cstring>using namespace std;int an[110],cn[110];int n,m;int summ=0;int dp[100010];int cnt[100010];void solve(){ int mark[100010]; memset(dp,0,sizeof(dp)); dp[0]=1; for(int i=1;i<=n;i++)//前i種硬幣可以組合出多少價值 { memset(cnt,0,sizeof(cnt)); for(int j=0;j<=m;j++) { if(dp[j]) continue;//如果價值為j的已經可行，就忽略這種情況 else if(j>=an[i]&&dp[j-an[i]]&&cnt[j-an[i]]<cn[i]) { dp[j]=dp[j-an[i]]; cnt[j]=cnt[j-an[i]]+1; //cnt[i]用來記錄已經使用的第i種硬幣的數目 } } } int ans=0; for(int i=1;i<=m;i++) if(dp[i]) ans++; cout<<ans<<endl; return;}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { // memset(dp,0,sizeof(mark)); if(n==0&&m==0) break; for(int i=1; i<=n; i++) scanf("%d",&an[i]); for(int i=1; i<=n; i++) scanf("%d",&cn[i]); //solve(0,1); //add.clear(); solve(); } return 0;}新聞熱點
疑難解答
