0-1 knapsack Problem问题背景超市赢家商品价格体积 啤酒2410 汽水23 饼干94 面包105 牛奶94超市允许顾客使用一个体积大小为13的背包选择一件或多件商品带走如何带走总价最多的商品inputn个商品组成的集合O每个商品有两个属性Vi体积Pi价格output求解一个商品子集S0- max蛮力枚举枚举共2n−12^n-12n−1种KnapsackSR(h,i,c)在第个到第个商品中容量为时最优解选择啤酒Knapsack(1,4,3)24不选择啤酒Knapsack(1,4,13)KnapsackSR(1,5,13)max{KnapsackSR(1,4,3)24,KnapsackSR(1,4,13)}—KnapsackSR(h,i,c)max{KnapsackSR(h,i-1,c-vi)pi,KnapsackSR(h,i,c)}//全局变量#defineINF1000000intp[MAXN],v[MAXN],;intmax(inta,intb){if(ab){returna;}elsereturnb;}intKnapsackSR(inth,inti,intc){if(c0){return-INF;}elseif(ih-1){return0;}intp,p1,p2;p1KnapsackSR(h,i-1,c-v[i])p[i];p2KnapsackSR(h,i-1,c);pmax(p1,p2);returnp;}选–KnapsackSR(h,i-1,c-vi)pi不选–pi,KnapsackSR(h,i,c)–精简掉hKnapsackSR(, )前个商品中容量为时最优解intmax(inta,intb){if(ab){returna;}elsereturnb;}intKnapsackSR(inti,intc){if(c0){return-INF;}elseif(i0){return0;}intp,p1,p2;p1KnapsackSR(i-1,c-v[i])p[i];p2KnapsackSR(i-1,c);pmax(p1,p2);//最优子问题returnp;}递归树时间复杂度O(2n)O(2^n)O(2n)重复的求解了大量子问题中间的(n-3,c-2v)这种是重复问题—做一个备忘录存住子问题如果有直接用没有再算他的值带备忘录的递归记录子问题的解避免重复计算KnapsackMR(i,c)intput:商品集合{1,…,i},背包容量coutput最大总价格P[ i , c ]//全局变量intP[MAX_N][MAX_C];//备忘录intv[MAX_N],p[MAX_N];//体积和价格intKnapsackMR(inti,intc){if(c0){return-INF;}elseif(i0){return0;}if(P[i][c]!NULL){//检查是否记录记录了就直接用returnP[i][c];}intp1,p2;p1KnapsackMR(i-1,c-v[i])p[i];//选第i个p2KnapsackMR(i-1,c);//不选第i个P[i][c]max(p1,p2);returnP[i][c];}p[i][c]p[i][c]p[i][c]表示在前i个商品中选择背包容量为c时的最优解自顶向下自底向上能否不递归直接求解p[i][c]p[i][c]p[i][c]?P[ i , c ]只有两种来源P[i-1,c]未选中P[i-1,c-vi]pi选中从左往右从上往下一行一行往下扫先要初始化给好p[0,c]p[i,0]都赋值为0给好初值实例找到了最优解那么如何确定选取了哪些商品呢递推求解最优解追踪递推公式[ , ] {[ − , − ] ,[ − , ]}记录决策过程rec [ i , c ] 1 选择商品 P[i,c] P[i-1,c-vi]pi 就要往回找去到P[i-1,c-vi] 0 不选商品 (P[i,c]P[i-1,c])就往上找去P[i-1,c]KnapsackDP(n,p,v,C)input:商品数量n,各商品的价值p各商品的体积u背包容量Coutput:商品价格的最大值最优解万案intKnapsackDP(intn,intC){for(inti0;iC;i){P[0][i]0;}for(inti0;in;i){P[i][0]0;}//初始化for(inti1;in;i){for(intc1;cC;c){if(v[i]c(p[i]P[i-1][c-v[i]]P[i-1][c]){//能选没超且应该选的确价格更高P[i][c]P[i-1][c-v[i]]p[i];rec[i][c]1;}else{//不选P[i][c]P[i-1][c];rec[i][c]0;}}}//输出最优方案intkC;for(intin;i1;i--){//倒着找if(rec[i][k]1){printf(选择物品 %d\n,i);kk-v[i];}else{printf(不选%d\n,i);}}returnP[n][C];}O(n * c)问题结构分析-递推关系建立-自底向上计算-最优方案追踪问题结构分析给出问题表示[, ]前个商品可选、背包容量为时的最大总价格递推关系建立分析最优子结构问题的最优解由相关子问题最优解组合而成子问题可以独立求解构造递推公式 , {[ −, ], [ − , − ]}自底向上计算确定计算顺序[, ]依赖于子问题[ − , −]和[ − , ]依次求解从左往右从上往下最优方案追踪记录决策过程rec [ i , c ]输出最优方案倒序判断是否选择商品 1 选择商品 P[i,c] P[i-1,c-vi]pi 就要往回找去到P[i-1,c-vi] 0 不选商品 (P[i,c]P[i-1,c])就往上找去P[i-1,c]如果要记录有几种方案
