题目描述： 题目链接：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;}新闻热点
疑难解答
