动态规划-最少硬币问题

来源：cnblogs　　作者：DNE　　时间：2018/10/15 9:05:48　　对本文有异议

问题描述：设有n种不同面值的硬币，各硬币的面值存在于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。对任意钱数0≤m≤20001，设计一个最少硬币找钱m的方法。

算法设计：对于给定的1≤n≤10 ，硬币面值数组T和可以使用的各种面值的硬币数组Coins，以及钱数m， 0≤m≤20001，计算找钱m的最少硬币数。

数据输入：由文件input. Txt提供输入数据，文件的第1行中只有一个整数给出n的值，第2行起每行两个数，分别是T[j]和Coins[j]。最后一行是要找的钱数m。

结果输出：将计算出的最少硬币数输出到文件output.txt。问题无解时输出-1。

输入文件示例input.txt：

1 3

2 3

5 3

输出文件示例output.txt：

关注点：

1.多重背包（每个物品有固定次数上限）

2.求的是最少

3.背包不能有空

代码：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 int maxint=2147483647;
 4 void getit(int* t,int* coin,int ncoin,int money,int **m)
 5 {
 6     m[ncoin][0]=0;
 7     for(int i=1;i<=money;i++)
 8     {
 9         m[ncoin][i]=maxint;
10         for(int j=1;j<=coin[ncoin];j++)
11           if(i==t[ncoin]*j)
12           {
13               m[ncoin][i]=j;
14               break;
15           } 
16     }
17       
18     for(int i=ncoin-1;i>=0;i--)
19     {
　　　　　　 //复制一遍
20         for(int j=0;j<=money;j++)
21           m[i][j]=m[i+1][j];
22         //修改到最佳 
23         for(int j=money;j>=t[i];j--)//从后往前做
　　　　　　 /*好处：不用考虑前面已经用了该面值的硬币多少个。m数组记录的不是单一面值硬币用到的个数，而是所有面值硬币用到的总个数
　　　　　　　　坏处：循环次数多了*/
24           for(int k=1;k<=coin[i];k++)
25             if((j-t[i]*k>=0)&&(m[i][j-t[i]*k]!=maxint)&&(m[i][j-t[i]*k]+k<m[i][j]))
26             m[i][j]=m[i][j-t[i]*k]+k;   
27     }
28     if(m[0][money]==maxint)printf("-1");
29     else printf("%d\n",m[0][money]);      
30       
31 }
32 
33  int main()
34  {
35     
　　　　//输入
　　　　int ncoin;
36     scanf("%d",&ncoin); 
37     int* t=(int *)malloc(sizeof(int)*ncoin);
38     int* coin=(int *)malloc(sizeof(int)*ncoin);
39     for(int i=0;i<ncoin;i++)
40       scanf("%d %d",&t[i],&coin[i]);
41     int money;
42     scanf("%d",&money);
　　　　//准备
43     int** m=(int **)malloc(sizeof(int *)*ncoin);
44     for(int i=0;i<ncoin;i++)
45       m[i]=(int *)malloc(sizeof(int)*(money+1));
46     int** num=(int **)malloc(sizeof(int *)*ncoin);
47     for(int i=0;i<ncoin;i++)
48       num[i]=(int *)malloc(sizeof(int)*(money+1));
　　　　//执行
49     getit(t,coin,ncoin-1,money,m);
　　　　//打印过程
50     for(int i=0;i<ncoin;i++)
51     {
52         for(int j=0;j<=money;j++)
53           printf("%d ",m[i][j]);
54         printf("\n");
55     }
56      return 0;
57  }