这个题目我一看就觉得是一个多重背包，但是呢，我不知道怎么输出路径，所以无可奈何，我就只能看一下题解了。

看了题解发现居然是把多重背包转化成完全背包，昨天学习了多重背包转化成01背包求解，今天又学习了这个。

 

题目大意：就是给你一个数字n，和1分钱的数量，5分钱的数量，10分钱的数量，25分钱的数量，

让你求组成这个数字n需要1分钱5分钱10分钱25分钱的数量，输出。

 

思路：

dp[i]定义为组成 i 的硬币数量最多为多少。

这个题目就是把硬币的价格当作容量，把硬币的数量当作数量，每一个硬币的价值都是1.

所以这个因为必须装满，所以dp[0]=0,其他都是-inf，转移方程就很简单了，这个具体看代码

最后就是一个路径记录，因为这个是多重背包，所以需要一个数组对某一种硬币使用数量进行限制。

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define inf 0x3f3f3f3fusing namespace std;const int maxn = 1e5 + 10;int dp[maxn], used[maxn], path[maxn];int weight[4] = { 1,5,10,25 };int main(){ int n, num[5]; while(scanf("%d%d%d%d%d",&n,&num[0],&num[1],&num[2],&num[3])!=EOF) { if (n == 0 && num[0] == 0 && num[1] == 0 && num[2] == 0 && num[3] == 0) break; memset(dp, -inf, sizeof(dp)); memset(path, 0, sizeof(path)); dp[0] = 0; path[0] = -1; for(int i=0;i<4;i++) { memset(used, 0, sizeof(used)); for(int j=weight[i];j<=n;j++) { if(dp[j-weight[i]]+1>dp[j]&&dp[j-weight[i]]>=0&&used[j-weight[i]]