思路：
多重背包转成01背包，怎么转？把一种大米看成一堆单个的物品，每件物品要么装入，要么不装。复杂度比01背包要大。时间复杂度为O(vns)（这里S是所有物品的数量s之和）。这个做法太粗糙了，但就是AC了。假如某一种大米有很多件，那麻烦大了。
0MS 1084K 706B C++
这是用“单纯转01背包”实现的，速度还这么快，还需优化不？
1 # include <stdio.h> 2 # include <string.h> 3 int dp[101] ;//转成01背包的解法，没有任何优化。 4 int max(int a,int b) 5 { 6 return a>b?a:b; 7 } 8 int main () 9 { 10 int T, ans, n, m ; 11 int p, h, c, i, j ; 12 scanf ("%d", &T) ; 13 while (T--) 14 { 15 scanf ("%d%d", &n, &m) ; //n是经费，m是种类 16 memset (dp, 0, sizeof(dp)) ; 17 ans = 0 ; 18 while (m--) 19 { 20 scanf ("%d%d%d", &p, &h, &c) ; 21 for(i = 1 ; i<=c ; i++) //m是经费 22 { 23 for(j = n ; j >= p ;j--) 24 { 25 dp[j]=max(dp[j],dp[j-p]+h); 26 } 27 } 28 } 29 printf ("%d ", dp[n]) ; 30 } 31 return 0 ; 32 }
未实现的想法：按照完全背包的做法，在里面加一些东西来控制“数量不够”的情况。当数量已达上限，用做大数量来代替，那么需要比较的两个dp值就是dp[j]与dp[j-1]，分别代表不装、装满。另用一个数组来记录每个不同的经费上限对应dp数组中所用的第i种大米的数量。这个数组要在不同i时更新为0，有开销。这个想法实现不了。
1 #include <iostream> 2 #define limit 110 3 using namespace std; 4 int p[limit]; //单价 5 int h[limit]; //净重 6 int c[limit]; //数量上限 7 int u[limit]; //已买的数量 8 int dp[limit]; 9 int max(int a,int b) 10 { 11 return a>b?a:b; 12 } 13 void cal(int n,int m) 14 { 15 int temp=0,j,i; 16 for(i=0;i<m;i++) 17 { 18 for(j=0;j<=n;j++) //初始化数组u 19 u[j]=0; 20 for( j=p[i];j<=n;j++) 21 { 22 temp=max( dp[j],dp[j-p[i]]+h[i] ); 23 if(temp==dp[j-p[i]]+h[i]) //需要加多一件 24 { 25 if(u[j-p[i]]<c[i]) //第i件还有剩余，可以买。 26 { 27 u[j]=u[j-p[i]]+1; 28 dp[j]=temp; 29 } 30 else //被用光了，但是为了防止前大于后的情况，在不能追加的情况下，仍需比较前后的大小，保证后总大于前 31 { 32 dp[j]=max(dp[j-1],dp[j]); //仅需比较1个，因前面每个所使用的并不是升序的，可能无序的 33 if(dp[j]==dp[j-1]) 34 u[j]=u[j-1];//因为u[j]本来就是0，所以else的情况不用赋零 35 } 36 } 37 } 38 } 39 return; 40 } 41 void main() 42 { 43 int q,n,m,i; 44 scanf("%d",&q); 45 while(q--) 46 { 47 memset(dp,0,sizeof(dp)); 48 scanf("%d%d",&n,&m); //经费的金额 大米的种类 49 for(i=0;i<m;i++) 50 { 51 scanf("%d%d%d",&p[i],&h[i],&c[i]); //分别表示每袋的价格、每袋的重量以及对应种类大米的袋数 52 } 53 cal(n,m); 54 printf("%d ",dp[n]); 55 } 56 }
可行的思路①：01背包+二进制法。 二进制的真谛啊。
1 #include <iostream> 2 #include <algorithm> 3 #define limit 110 4 using namespace std; 5 int p[limit]; //单价 6 int h[limit]; //净重 7 int c[limit]; //数量上限 8 int dp[limit]; 9 10 int max(int a,int b) 11 { 12 return a>b?a:b; 13 } 14 void cal(int n,int m) 15 { 16 int temp=0,j,i,k,nCount; 17 for(i=0;i<m;i++) 18 { 19 k = 1; 20 nCount = c[i]; 21 while(k <= nCount) 22 { 23 for( j=n;j>=k*p[i];j--) 24 { 25 dp[j] = max(dp[j],dp[j - k*p[i]] + k*h[i]); 26 } 27 nCount -= k; 28 k <<= 1; // <<就是左移 29 } 30 if(nCount!=0) // 不是刚好2的几次方，另外处理 31 for( j=n; j>=nCount*p[i] ;j-- ) 32 { 33 dp[j] = max( dp[j] , dp[j - nCount*p[i]] + nCount*h[i] ); 34 } 35 } 36 } 37 void main() 38 { 39 int q,n,m,i; 40 scanf("%d",&q); 41 while(q--) 42 { 43 memset(dp,0,sizeof(dp)); 44 scanf("%d%d",&n,&m); //经费的金额 大米的种类 45 for(i=0;i<m;i++) 46 { 47 scanf("%d%d%d",&p[i],&h[i],&c[i]); //分别表示每袋的价格、每袋的重量以及对应种类大米的袋数 48 } 49 cal(n,m); 50 printf("%d ",dp[n]); 51 } 52 }
讲一下用01背包+二进制法：将每种大米的件数分成1,2,4,8,16,32....这么多份，即1+2+4+8+....=第i种大米的件数。 在分的时候最后一件不一定刚好是2的几次方形式，是多少就是多少，待单独处理。那么假如13就分成了1，2，4，6了，这里的6就是不足2^3=8才是6的。在单纯转01背包的方式中，每种大米的每一件都单独处理，而二进制法是将分好的几件归为一件对待。比如第一种大米是13件，在单纯转01背包时，最里层是需要13次循环的，但是在二进制法的01背包中，它被分成1，2，4，6件共4堆，我们把每堆当成一件，捆绑在一起的，在更新dp数组的时候按大小的顺序来循环，即第1次循环是1件，第2次循环是2件套装，第3次循环是4件套，第4次循环是6件套。这里的最里层循环就变成了4次循环了。减少的计算量是很客观的。
15MS 1096K 1030B c++
可行的思路②：在转成01背包上作优化。完全背包+01背包来解，即：某一种大米的数量*单价>=经费，那么就是完全背包型；否则就是01背包型。但如果遇到都是01背包型，此优化没用了。
1 #include <iostream> 2 #include <algorithm> 3 #define limit 110 4 using namespace std; 5 int p[limit]; //单价 6 int h[limit]; //净重 7 int c[limit]; //数量上限 8 int dp[limit]; 9 int n,m; 10 int max(int a,int b) 11 { 12 return a>b?a:b; 13 } 14 void _01pack(int n_p,int n_h) //01背包 15 { 16 for (int j = n;j >= n_p;j--) 17 { 18 dp[j] = max(dp[j],dp[j - n_p] + n_h); 19 } 20 } 21 void cpack(int n_p,int n_h) //完全背包 22 { 23 for (int j = n_p;j <= n;j++) 24 { 25 dp[j] = max(dp[j],dp[j - n_p] + n_h); 26 } 27 } 28 29 30 void cal() 31 { 32 int i,k,nCount; 33 for(i=0;i<m;i++) 34 { 35 if (p[i] * c[i] >= n) 36 cpack(p[i],h[i]); 37 else 38 { 39 k = 1; 40 nCount = c[i]; 41 while(k <= nCount) 42 { 43 _01pack(k * p[i],k * h[i]); 44 nCount -= k; 45 k *= 2; 46 } 47 _01pack(nCount * p[i],nCount * h[i]); 48 } 49 } 50 } 51 void main() 52 { 53 int q,i; 54 scanf("%d",&q); 55 while(q--) 56 { 57 memset(dp,0,sizeof(dp)); 58 scanf("%d%d",&n,&m); //经费的金额 大米的种类 59 for(i=0;i<m;i++) 60 { 61 scanf("%d%d%d",&p[i],&h[i],&c[i]); //分别表示每袋的价格、每袋的重量以及对应种类大米的袋数 62 } 63 cal(); 64 printf("%d ",dp[n]); 65 } 66 }
15MS 1096K 1181B c++
其他可行的思路：队列法。复杂度为O（vn），还没理解。所以没代码。