首页 > 代码库 > 混合背包（背包03）
混合背包（背包03）
将01背包，完全背包，和多重完全背包问题结合起来，那么就是混合三种背的问题
根据三种背包的思想，那么可以得到
混合三种背包的问题可以这样子求解
for(int i=1; i<=N; ++i)
if(第i件物品是01背包)
zeroOnePack(c[i],w[i]);
else if(第i件物品是完全背包)
completePack(c[i],w[i]);
else if(第i件物品是多重完全背包)
multiplePack(c[i],w[i],n[i]);
这样能得到最优解的原因是，因为前一层已经是得到最优解了，
当前层求解最优解的时候，我们考虑要使用三种背包中的哪一种方法
而不用考虑前一层是怎么得到最优解的
#include <stdio.h>#include <string.h>int cash;int n[11],dk[11];int dp[1000000];inline int max(const int &a, const int &b){ return a < b ? b : a;}void CompletePack(int cost){ for(int i=cost; i<=cash; ++i) dp[i] = max(dp[i],dp[i-cost]+cost);}void ZeroOnePack(int cost){ for(int i=cash; i>=cost; --i) dp[i] = max(dp[i],dp[i-cost]+cost);}void MultiplePack(int cnt, int cost){ if(cnt*cost >=cash)//如果第i种物品的费用总和超过背包容量，那么就是完全背包问题 CompletePack(cost); else { int k = 1;//二进制拆分 while(k<cnt)//判断剩下的数字能不能够拆分为k { ZeroOnePack(cost*k); cnt -=k; k<<=1; } ZeroOnePack(cnt*cost); }}int main(){ //输入的处理以及函数的调用 return 0;}
如果对你有所帮助，别忘了加好评哦；么么哒！！下次见！88
混合背包（背包03）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。