背包九讲之四（混合三种背包问题）

1 /* 2 将01背包，完全背包，和多重完全背包问题结合起来，那么就是混合三种背的问题 3 根据三种背包的思想，那么可以得到 4 混合三种背包的问题可以这样子求解 5 for(int i=1; i<=N; ++i) 6 if(第i件物品是01背包) 7 zeroOnePack(c[i],w[i]); 8 else if(第i件物品是完全背包) 9 completePack(c[i],w[i]); 10 else if(第i件物品是多重完全背包) 11 multiplePack(c[i],w[i],n[i]); 12 13 这样能得到最优解的原因是，因为前一层已经是得到最优解了， 14 当前层求解最优解的时候，我们考虑要使用三种背包中的哪一种方法 15 而不用考虑前一层是怎么得到最优解的 16 */ 17 18 #include <stdio.h> 19 #include <string.h> 20 int cash; 21 int n[11],dk[11]; 22 int dp[1000000]; 23 inline int max(const int &a, const int &b) 24 { 25 return a < b ? b : a; 26 } 27 void CompletePack(int cost) 28 { 29 for(int i=cost; i<=cash; ++i) 30 dp[i] = max(dp[i],dp[i-cost]+cost); 31 } 32 void ZeroOnePack(int cost) 33 { 34 for(int i=cash; i>=cost; --i) 35 dp[i] = max(dp[i],dp[i-cost]+cost); 36 } 37 void MultiplePack(int cnt, int cost) 38 { 39 if(cnt*cost >=cash)//如果第i种物品的费用总和超过背包容量，那么就是完全背包问题 40 CompletePack(cost); 41 else 42 { 43 int k = 1;//二进制拆分 44 while(k<cnt)//判断剩下的数字能不能够拆分为k 45 { 46 ZeroOnePack(cost*k); 47 cnt -=k; 48 k<<=1; 49 } 50 ZeroOnePack(cnt*cost); 51 } 52 } 53 int main() 54 { 55 //输入的处理以及函数的调用 56 return 0; 57 }

 

转载于:https://www.cnblogs.com/justPassBy/p/4279238.html

总结

以上是生活随笔为你收集整理的背包九讲之四（混合三种背包问题）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。