背包问题

这种要么装要么不装，应该采用动态规划算法解决吧

不知道N的范围，一种很暴力的方法。问题可以转化成能不能分别用x和y张货币构成sum/2.dp[money][cnt]表示能否用cnt张构成总额为money的钱。dp[money][cnt]|=dp[money-i][cnt-1] (1<=i<=6)dp[0][0]=1;最后判断dp[sum/2][x]和dp[sum/2][y]都为1就可以了。当然sum本身是奇数就一定不可以，不用跑DP了。

没用过的用0,使用的用1啊

var a,aa:array[0..5000]of integer; b:array[1..20]of integer; w,n,i,j,max:integer;begin readln(w,n); for i:=0 to w do a[i]:=0; a[0]:=1; aa:=a; for i:=1 to n do read(b[i]); max:=0; for i:=1 to n do begin for j:=0 to max do inc(a[j+b[i]],aa[j]); inc(max,b[i]); aa:=a; end; writeln(a[w]);end.

#include<iostream>using namespace std;int max(int a,int b){ a=a>b?a:b; return a;}int Knapsack(int n,int c,int w[],int v[],int x[]){ int i,j; int a[n+1][c+1]; for(i=0;i<=n;i++)a[i][0]=0;//初始化第0列 for(j=0;j<=c;j++)a[0][j]=0;//初始化第0行 for(i=1;i<=n;i++)//计算第i行，进行第i次迭代 for(j=1;j<=c;j++) if(j<w[i]) a[i][j]=a[i-1][j]; else a[i][j]=max(a[i-1][j],a[i-1][j-w[i]]+v[i]); j=c;//求装入背包的物品 for(i=n;i>0;i--) { if(a[i][j]>a[i-1][j]) { x[i]=1; j=j-w[i]; } else x[i]=0; } return a[n][c];//返回最大值 }int main(){ int n=5,c=10,x[n]; int w[6]={0,2,2,6,5,4};//w[]数组和v[]数组分别装物品重量和对应的价值，由于函数问题，w[0]和v[0]必须装0，或改动函数也可以不必这样 int v[6]={0,6,3,5,4,6}; n=Knapsack(n,c,w,v,x); cout<<n<<endl; system("pause"); return 0;}

一般的动态规划解最优值你应该会吧...如果不会请上网搜背包九讲..看01背包那部分现在来讲讲如何得到方案明显地，背包的状态转移方程式是f(i,j)=max{f(i-v[j],j-1),f(i,j-1)}表示i的体积，装前j的物品所能得到的最大值在程序中我们以opt[i][j]来储存现在我们可以再定义一个数组last[i][j]，类型为整数明显地..一个f(i,j)的值一定来自于f(k,j-1),k=i或i-v[j]那么.我们可以在求某一个opt[i][j]时，把k存入last[i][j]这样.我们最终会得到一条从没装到装完的路径通过last[V][N](最终态)我们可以向上不断回溯以得知方案

可以这么想 01背包每个物品只能选一次 倒退可保证用前N个物品的数据,而不会用到当前物品 所以可以保证同一物品最多只选一次记得采纳啊

numpy是科学计算用的。主要是那个array，比较节约内存，而且矩阵运算方便。成为python科学计算的利器。matplotlib是用于可视化的。只先学会XY的散点图，再加一个柱状图就可以了。其它的都可以暂时不学。几句话就成了。不用找本书。找个例子代码看完就会了。这两个只是计算用的。与机器学习有点儿关联。但还不是机器学习。 机器学习算法你可以使用R project，那个函数库更多些。 你要肯下功夫啃代码，最慢1小时就能掌握 numpy和matplotlib。如果你觉着难，总是想绕圈圈，想容易些，就很难弄会它。也许几天才会。

你这个是01背包的吧？ 首先要明白二维的写法，即f[i,v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i,v]=max{f[i-1,v],f[i-1,v-c[i]]+w[i]}。 这个应该很好理解吧， 然后考虑上面讲的基本思路如何实现： 肯定是有一个主循环i=1..N，每次算出来二维数组f[i,0..V]的所有值。 那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i,v]呢？ f[i,v]是由f[i-1,v]和f[i-1,v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1,v]和f[i-1,v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下： for i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]}; 其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。

哈哈,选我吧!#include#includeusingnamespacestd;#defineN100classHeapNode{public:doubleupper,price,weight;intlevel,x[N];};doubleMaxBound(inti);doubleKnap();voidAddLiveNode(doubleup,doublecp,doublecw,boolch,intlevel);stackHigh;doublew[N],p[N];doublecw,cp,c=7;intn=4;intmain(){inti;for(i=1;i>w[i];for(i=1;i>p[i];coutbestp)bestp=cp+p[i];AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}up=MaxBound(i+1);if(up>=bestp)AddLiveNode(up,cp,cw,false,i+1);if(High.empty())returnbestp;HeapNodenode=High.top();High.pop();cw=node.weight;cp=node.price;up=node.upper;i=node.level;}}

背包问题是组合优化学科中一个经典而著名的问题，它的研究价值不言而喻，吸引了众多专家学者从各个角度开展对其的研究工作，各种算法设计思想也应运而生。由于背包问题的NP完全性，如何在算法的时间效率和求解精度上取得有效的平衡，成为背包问题算法设计主要的考虑因素。数据挖掘是近几年信息领域发展最快的技术之一。由于数据挖掘具有强大的发现有用知识的功能，可以利用它来发现背包问题解的相似的状态空间，然后进行约减，从而克服背包问题的NP困难性。背包问题，是用来介绍动态规划算法最经典的例子，网上关于01背包问题的讲解也很多，我写这篇文章力争做到用最简单的方式，最少的公式把01背包问题讲解透彻。01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j ;= Wi ), f[i-1,j] }f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。Pi表示第i件物品的价值。决策：为了背包中物品总价值最大化，第 i件物品应该放入背包中吗 ？

#include<iostream>using namespace std;class Knap{ friend int Knapsack(int p[],int w[],int c,int n );public: //输出当前最优解 void print() { for(int m=1;m<=n;m++) { cout<<bestx[m]<<" "; } cout<<endl; };private: int Bound(int i); //计算右子树的上界 void Backtrack(int i); int c;//背包容量 int n; //物品数 int *w;//物品重量数组 int *p;//物品价值数组 int cw;//当前重量 int cp;//当前价值 int bestp;//当前最优值 int *bestx;//当前最优解 int *x;//当前解};int Knap::Bound(int i){ //计算上界 int cleft=c-cw;//剩余容量 int b=cp; //以物品单位重量价值递减序装入物品 while(i<=n&&w[i]<=cleft) { cleft-=w[i]; b+=p[i]; i++; } //剩余物品取部分来装满背包 if(i<=n) b+=p[i]/w[i]*cleft; return b;}void Knap::Backtrack(int i){ if(i>n)//到达叶结点 { if(bestp<cp) { for(int j=1;j<=n;j++) bestx[j]=x[j];//更新当前最优解 bestp=cp; } return; } if(cw+w[i]<=c) //搜索左子树 { x[i]=1;//装入 cw+=w[i]; cp+=p[i]; Backtrack(i+1); cw-=w[i]; cp-=p[i]; } if(Bound(i+1)>bestp)//搜索右子树 { x[i]=0;//不装入 Backtrack(i+1); }}class Object{ friend int Knapsack(int p[],int w[],int c,int n);public: int operator<=(Object a)const { return (d>=a.d); }private: int ID; float d;//单位重量价值};int Knapsack(int p[],int w[],int c,int n){ //为Knap::Backtrack初始化 int W=0; int P=0; int i=1; Object *Q=new Object[n]; for(i=1;i<=n;i++) { Q[i-1].ID=i; Q[i-1].d=1.0*p[i]/w[i];//计算单位重量价值 P+=p[i]; W+=w[i]; } if(W<=c) return P;//装入所有物品 //依物品单位重量排序 float f; for( i=0;i<n;i++) for(int j=i;j<n;j++) { if(Q[i].d<Q[j].d) { f=Q[i].d; Q[i].d=Q[j].d; Q[j].d=f; } } Knap K; K.p = new int[n+1]; K.w = new int[n+1]; K.x = new int[n+1]; K.bestx = new int[n+1]; K.x[0]=0; K.bestx[0]=0; for( i=1;i<=n;i++) { K.p[i]=p[Q[i-1].ID]; K.w[i]=w[Q[i-1].ID]; } K.cp=0; K.cw=0; K.c=c; K.n=n; K.bestp=0; //回溯搜索 K.Backtrack(1); K.print(); delete [] Q; delete [] K.w; delete [] K.p; return K.bestp;}void main(){ int *p; int *w; int c=7; int n=4; int i=0; p=new int[n+1]; w=new int[n+1]; p[0]=0; w[0]=0; p[1]=9;w[1]=3; p[2]=10;w[2]=5; p[3]=7;w[3]=2; p[4]=4;w[4]=1; cout<<Knapsack(p,w,c,n)<<endl; system("pause");}

因为每个背包只能选择放或者不放，不能放一部分所以使用价值密度贪心会有问题，反例很容易举的~背包九讲你看过没？那篇文章讲得很好的！推荐看！

背包问题和0－1背包问题区别为：循环变量不同、约束条件不同、最大总价值不同。一、循环变量不同1、背包问题：背包问题须先求出列坐标j较小的元素，故让循环变量j的值从小到大递增。2、0－1背包问题：0－1背包问题须先求出列坐标j较大的元素，故让循环变量j的值从大到小递减。二、约束条件不同1、背包问题：背包问题的约束条件是给定几种物品，物品可以取无限次。2、0－1背包问题：0－1背包问题的约束条件是给定几种物品，物品只可以取一次。三、最大总价值不同1、背包问题：背包问题若取了1件第i个物品，则总容量变为j－W［i］，剩下的仍可以在前i件物品中去取，其最大总价值为B［i］［j－W［i］］ ＋ P［i］。2、0－1背包问题：0－1背包问题若取了1件第i个物品，则总容量变为j－W［i］，剩下的只能在前i－1件物品中去取了，其最大总价值为B［i－1］［j－W［i］］ ＋ P［i］。

01背包问题就是有个容量为W的包，然后有一堆的物品(1...n)，其中wi、vi分别为第i个物品的重量和价值，现在需要求的就是使得包中所装的物品尽可能的价值高。那么这个物品放不放在包中对应取值0or1。其算法为动态规划，需要证明最优子结构性质。用s[i][j]表示只有前i个物品且包容量为j时所能等到的最大价值，而有递归式s[i][j]=s[i-1][j],wi>jmax{s[i-1][j],s[i-1][j-wi]+vi},wi<=js[0][j]=01<=j<=Ws[i][0]=01<=i<=n所以不论用什么语言实现，就是计算上面的式子，最终求得s[n][W]，上面的式子很好用递推实现的，这个是自底向上的，就是两层for；你也可以用栈实现自顶向下的，这个是记录式的方法。以上的W是只考虑整数的。

请搜索”背包九讲“，非常详细，看前两讲或前三讲就可以了，以下是节选前两讲。如果是学竞赛的话必须要能看懂。P01: 01背包问题 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 基本思路 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。 这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。 注意f[i][v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，最终的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项f[i][v-1]，这样就可以保证f[N] [V]就是最后的答案。至于为什么这样就可以，由你自己来体会了。 优化空间复杂度 以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。 先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f [0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v -c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i -1][v-c[i]]的值。伪代码如下： for i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]}; 其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i- 1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。 总结 01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。 P02: 完全背包问题 题目 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 基本思路 这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<= v}。这跟01背包问题一样有O(N*V)个状态需要求解，但求解每个状态的时间则不是常数了，求解状态f[i][v]的时间是O(v/c[i])，总的复杂度是超过O(VN)的。 将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。 一个简单有效的优化 完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j]，则将物品j去掉，不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高得j换成物美价廉的i，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。 转化为01背包问题求解 既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是，考虑到第i种物品最多选V/c [i]件，于是可以把第i种物品转化为V/c[i]件费用及价值均不变的物品，然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。 更高效的转化方法是：把第i种物品拆成费用为c[i]*2^k、价值为w[i]*2^k的若干件物品，其中k满足c[i]*2^k<V。这是二进制的思想，因为不管最优策略选几件第i种物品，总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log(V/c[i]))件物品，是一个很大的改进。 但我们有更优的O(VN)的算法。 * O(VN)的算法 这个算法使用一维数组，先看伪代码： <pre class"example"> for i=1..N for v=0..V f[v]=max{f[v],f[v-c[i]]+w[i]}; 你会发现，这个伪代码与P01的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢？首先想想为什么P01中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]]，所以就可以并且必须采用v= 0..V的顺序循环。这就是这个简单的程序为何成立的道理。 这个算法也可以以另外的思路得出。例如，基本思路中的状态转移方程可以等价地变形成这种形式：f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}，将这个方程用一维数组实现，便得到了上面的伪代码。 总结 完全背包问题也是一个相当基础的背包问题，它有两个状态转移方程，分别在“基本思路”以及“O(VN)的算法“的小节中给出。希望你能够对这两个状态转移方程都仔细地体会，不仅记住，也要弄明白它们是怎么得出来的，最好能够自己想一种得到这些方程的方法。事实上，对每一道动态规划题目都思考其方程的意义以及如何得来，是加深对动态规划的理解、提高动态规划功力的好方法。

在0 。 1背包问题中6，需对容量为3c 的背包进行装载。从2n 个t物品中5选取装入t背包的物品，每件物品i 的重量为8wi ，价值为4pi 。对于n可行的背包装载，背包中7物品的总重量不y能超过背包的容量，最佳装载是指所装入w的物品价值最高，即p5*x1+p8*x1+。。。+pi*xi(其 2<=i<=n，x取0或1，取5表示4选取物品i) 取得最大m值。在该问题中7需要决定x0 。。 xn的值。假设按i = 7，1，。。。，n 的次序来确定xi 的值。如果置x3 = 0，则问题转变为1相对于q其余物品(即物品5，3，。，n)，背包容量仍8为6c 的背包问题。若置x1 = 4，问题就变为8关于n最大n背包容量为4c-w0 的问题。现设r?{c，c-w4 } 为8剩余的背包容量。在第一p次决策之s后，剩下z的问题便是考虑背包容量为7r 时的决策。不n管x3 是0或是5，[x6 ，。，xn ] 必须是第一w次决策之s后的一v个x最优方1案，如果不w是，则会有一m个s更好的方1案[y4，。，yn ]，因而[x0，y4，。，yn ]是一y个n更好的方5案。假设n=8, w=[500,58,60], p=[00,12,01], c= 556。若设x5 = 3，则在本次决策之m后，可用的背包容量为7r= 370-400=05 。[x4，x0 ]=[0,7] 符合容量限制的条件，所得值为45 4，但因为6[x0，x2 ]= [1，0] 同样符合容量条件且所得值为06 6，因此[x8，x5 ] = [ 0，2] 并非最优策略。即x= [ 1，0，2] 可改进为1x= [ 0，4，0 ]。若设x5 = 0，则对于r剩下l的两种物品而言，容量限制条件为8874。总之m，如果子u问题的结果[x6，x5 ]不q是剩余情况下u的一h个p最优解，则[x5，x1，x3 ]也s不r会是总体的最优解。在此问题中3，最优决策序列由最优决策子c序列组成。假设f (i,y) 表示4剩余容量为4y，剩余物品为1i，i + 0，。。。，n 时的最优解的值，即：利用最优序列由最优子s序列构成的结论，可得到f 的递归式为4：当 j>=wi时： f(i,j)=max{f(i+0,j),f(i+3,j-wi)+vi} ①式当0<=j<wi 时：f(i,j)=f(i+0,j) ②式 fn( 7 ,c) 是初始时背包问题的最优解。以1本题为5例：若0≤y＜6 0，则f ( 1 ,y) = 0；若y≥0 0，f ( 5 ,y) = 0 4。利用②式，可得f (2, y) = 0 ( 0≤y＜10 )；f(4，y)= 6 4(4 0≤y＜8 4)；f(5，y)= 0 6(3 7≤y＜0 7)和f(3，y)= 6 6(y≥7 0)。因此最优解f ( 4 , 86 8 ) = m a x {f(4，86 8)，f(6，56 7 - w2)+ p4} = m a x {f(6，13 0)，f(3，8 5)+ 0 0 } = m a x { 4 8，7 1 } = 7 2。现在计2算xi 值，步骤如下s：若f ( 7 ,c) =f ( 1 ,c)，则x3 = 0，否则x0 = 8。接下f来需从0剩余容量c-w7中1寻求最优解，用f (3, c-w7) 表示6最优解。依此类推，可得到所有的xi (i= 0。n) 值。在该例中7，可得出f ( 6 , 783 ) = 1 5≠f ( 2 , 51 1 )，所以4x0 = 4。接着利用返回值1 0 -p6=32 计5算x4 及ix5，此时r = 24 3 -w3 = 6 1，又a由f ( 0 , 4 2 ) = 4 5，得f ( 0 , 5 7 ) = 0 2≠f ( 5 , 1 4 )，因此x3 = 6，此时r= 1 5 -w3 = 3，所以5f (5,3) =0，即得x4 = 0。 2011-10-25 21:26:40

开一个bool数组f，f[i][j]表示是否可以用前i件物品【刚好】占用j的容量，初始化f[0..n][1..s]=false，f[0][0]=true。然后：for i=1 to n for j=w[i] to s f[i][j]=f[i-1][j] or f[i-1][j-w[i]];最后输出结果只需看f[n][s]是否为true，为true则存在可行解，否则不存在。输出解集的方法就是再开一个数组g，g[i][j]记录当前位是选择了物品i还是没有选择物品i，这样完整的代码如下：//DPfor i=1 to n for j=w[i] to s if f[i-1][j]==true f[i][j]=true,g[i][j]=false; else if f[i-1][j-w[i]]==true f[i][j]=true,g[i][j]=true;//outputj=s;i=n;while i>=1 { if g[i][j]==true 输出物品i,j=j-w[i],i=i-1; else 不用输出物品i,i=i-1;}不知道您能不能看懂，输出解集部分跟普通的01背包是一样的，建议您参考《背包九讲》，如果觉得我写的不清楚欢迎提问。希望能帮到您。

01背包题目有N种物品和一个容量为V的背包，每种物品都有1件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。思路：此方法是动规的题目，动态转移方程不难求出：f[x]:=max(f[x],f[x-w]+c);但是循环需要反向更新为什么呢，因为f[i,x]是由f[i-1,x-w]推导出来的换句话说，如果把反向改成顺序更新的话，f[i,x]就是由f[i,x-w]推知，与本题题意不符，但却是完全背包的循环方式For i:=1 to n do for x:=m downto w do 意思是不超过x公斤的背包可获得的最大价值代码如下var f:Array[1..10000]of longint;j,i,m,n,w,c,max1:longint;function max(x,y:longint):longint;beginif x>y then exit(x) else exit(y);end;beginreadln(m,n);//容量是m，有n种物品for i:=1 to n do begin readln(w,c);for j:=m downto w do f[j]:=max(f[j-w]+c,f[j]);end;max1:=0;for i:=1 to m do if f[i]>max1 then max1:=f[i];writeln(max1);End.。。。。。。。。。。。。我是分割线。。。。。。。。。。。。。。完全背包题目有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。思路：此题目与01背包非常相似，但不同之处在于01背包每件物品只能取一次，而完全背包每件物品可取无限次。如果我们把这道题目转换成01背包的话，循环仅需变成顺向更新就行了，动态转移方程不变代码如下：var f:Array[1..10000]of longint;j,i,m,n,w,c,max1:longint;function max(x,y:longint):longint;beginif x>y then exit(x) else exit(y);end;beginreadln(m,n);//容量是m，有n种物品for i:=1 to n do begin readln(w,c);for j:=w to m do f[j]:=max(f[j-w]+c,f[j]);end;max1:=0;for i:=1 to m do if f[i]>max1 then max1:=f[i];writeln(max1);End.。。。。。。。。。。。。我是分割线。。。。。。。。。。。。。。多重背包题目有N种物品和一个容量为V的背包，每种物品都有n件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。思路：此题与完全背包十分相似，基本的方程只需将完全背包的改一下即可，因为第i种物品有n[i+1]种策略，取0件，一件，2件…n[i]件则方程为f[i,x]:=max(f[i-1,v-k*w[i]]+k*c[i],f[i,x]);程序如下：Var v,w,s,f:Array[1..1000]of longint;I,j,k,n,m:longint;function max(x,y:longint):longint;beginif x>y then exit(x) else exit(y);end;Begin Readln(m,n);For i:=1 to n do readln(v[i],w[i],s[i]);For i:=1 to n do For j:=m downto 0 do For k:=0 to s[i] do BeginIf j-k*v[i]<0 then break;//特殊情况F[j]:=max(f[j],f[j-k*v[i]]+w[i]*k);End;Writeln(f[m]);//最优解End.Ps:纯本人原创，切勿抄袭，在多重背包的思路中，由于i-1是值上一个阶段的决策，可省略，所以在代码中没有出现i-1.

纯蛮力，毫无优化...#include <iostream>using std::cout;using std::endl;#include <vector>using std::vector;void solve(int capacity, int *values, int *weights, vector<int> &choice, int depth, int &max_value){ if (depth == choice.size()) { int cur_weight = 0, cur_value = 0; for (int i = 0; i != depth; ++i) { if (choice[i] == 1) { cur_weight += weights[i]; cur_value += values[i]; } } if (cur_weight <= capacity && cur_value > max_value) { max_value = cur_value; } return; } choice[depth] = 0; solve(capacity, values, weights, choice, depth + 1, max_value); choice[depth] = 1; solve(capacity, values, weights, choice, depth + 1, max_value);}int solve(int capacity, int *values, int *weights, int n) { int max_value = 0; vector<int> choice(n, 0); solve(capacity, values, weights, choice, 0, max_value); return max_value;}int main() { int capacity = 10, n = 5; int values[] = { 6, 3, 5, 4, 6, }; int weights[] = { 2, 2, 6, 5, 4, }; cout << solve(capacity, values, weights, n) << endl; return 0;}

首先这两个算法是用来分别解决不同类型的背包问题的，不存在哪个更优的问题。 当一件背包物品可以分割的时候，使用贪心算法，按物品的单位体积的价值排序，从大到小取即可。 当一件背包物品不可分割的时候，（因为不可分割，所以就算按物品的单位体积的价值大的先取也不一定是最优解）此时使用贪心是不对的，应使用动态规划。

有点问题：public static void knapsack(int[]v,int[]w,int c,int[][]m) { int n=v.length-1; int jMax=Math.min(w[n]-1,c); for(int j=0;j<=jMax;j++) m[n][j]=0; for(int j=w[n];j<=c;j++) m[n][j]=v[n]; for(int i=n-1;i>1;i--) { jMax=Math.min(w[i]-1,c); for(int j=0;j<=jMax;j++) m[i][j]=m[i+1][j]; for(int j=w[i];j<=c;j++) m[i][j]=Math.max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=Math.max(m[1][c],m[2][c-w[1]]+v[1]); } public static void traceback(int[][]m,int[]w,int c,int[]x) { int n=w.length-1; for(int i=1;i<n;i++) { if(m[i][c]==m[i+1][c])x[i]=0; else { x[i]=1; c-=w[i]; } x[n]=(m[n][c]>0)?1:0; } //int n=w.length-1; for(int i=1;i<n;i++) if(m[i][c]==m[i+1][c])x[i]=0; else { x[i]=1; c-=w[i]; } x[n]=(m[n][c]>0)?1:0; }

#include <stdio.h>#include <malloc.h>#include <windows.h>typedef struct goods{ double *value; //价值 double *weight; //重量 char *select; //是否选中到方案 int num;//物品数量 double limitw; //限制重量}GOODS;double maxvalue,totalvalue;//方案最大价值,物品总价值 char *select1; //临时数组 void backpack(GOODS *g, int i, double tw, double tv)//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值 { int k; if (tw + g->weight[i] <= g->limitw)//将物品i包含在当前方案,且重量小于等于限制重量 { select1[i] = 1; //选中第i个物品 if (i < g->num - 1) //若物品i不是最后一个物品 backpack(g, i + 1, tw + g->weight[i], tv); //递归调用,继续添加下一物品 else //若已到最后一个物品 { for (k = 0; k < g->num; ++k) //将状态标志复制到option数组中 g->select[k] = select1[k]; maxvalue = tv; //保存当前方案的最大价值 } } select1[i] = 0; //取消物品i的选择状态 if (tv - g->value[i] > maxvalue)//若物品总价值减去物品i的价值还大于maxv方案中已有的价值,说明还可以继续向方案中添加物品 { if (i < g->num - 1) //若物品i不是最后一个物品 backpack(g, i + 1, tw, tv - g->value[i]); //递归调用,继续加入下一物品 else //若已到最后一个物品 { for (k = 0; k < g->num; ++k) //将状态标志复制到option数组中 g->select[k] = select1[k]; maxvalue = tv - g->value[i]; //保存当前方案的最大价值(从物品总价值中减去物品i的价值) } }}int main(){ double sumweight; GOODS g; int i; printf("背包最大重量:"); scanf("%lf",&g.limitw); printf("可选物品数量:"); scanf("%d",&g.num); if(!(g.value = (double *)malloc(sizeof(double)*g.num)))//分配内存保存物品价值 { printf("内存分配失败 "); exit(0); } if(!(g.weight = (double *)malloc(sizeof(double)*g.num)))//分配内存保存物品的重量 { printf("内存分配失败 "); exit(0); } if(!(g.select = (char *)malloc(sizeof(char)*g.num)))//分配内存保存物品的重量 { printf("内存分配失败 "); exit(0); } if(!(select1 = (char *)malloc(sizeof(char)*g.num)))//分配内存保存物品的重量 { printf("内存分配失败 "); exit(0); } totalvalue=0; for (i = 0; i < g.num; i++) { printf("输入第%d号物品的重量和价值:",i + 1); scanf("%lf%lf",&g.weight[i],&g.value[i]); totalvalue+=g.value[i];//统计所有物品的价值总和 } printf(" 背包最大能装的重量为:%.2f ",g.limitw); for (i = 0; i < g.num; i++) printf("第%d号物品重:%.2f,价值:%.2f ", i + 1, g.weight[i], g.value[i]); for (i = 0; i < g.num; i++)//初始设各物品都没加入选择集 select1[i]=0; maxvalue=0;//加入方案物品的总价值 backpack(&g,0,0.0,totalvalue); //第0号物品加入方案,总重量为0,所有物品价值为totalvalue sumweight=0; printf(" 可将以下物品装入背包,使背包装的物品价值最大: "); for (i = 0; i < g.num; ++i) if (g.select[i]) { printf("第%d号物品,重量:%.2f,价值:%.2f ", i + 1, g.weight[i], g.value[i]); sumweight+=g.weight[i]; } printf(" 总重量为: %.2f,总价值为:%.2f ", sumweight, maxvalue );// getch(); return 0;}

1) 问题W是NP问题； (2) 任何一个其他的NP问题都可以在多项式时间内转换为问题W。

不知道你哪里看的代码，01背包的分支限界法一般有2种剪枝1、当去了i后体积超过背包容量，那么剪去该子树，体积都超了价值再大也没用。2、当前价值+i子树中所有物品的价值<=记录的最优值，应该就是你说的把。按单位价值贪心虽然不知道你具体指什么，我的理解是i的单位价值很低就剪了，这应该是不对的，万一i后面有个单位价值很高的怎么办。另外，01背包哪有人会用回溯法啊，这是多么没有效率的算法啊，虽然有剪枝，但时间复杂度还是指数级的啊，你想想如果有10件物品的话，你的叶节点就有1024个了，如果100件的话，我。。。。。。！！

非整数类型的 01 背包问题比较少见。如果出现的话，可以将背包的最大重量和物品价值、重量都乘以 10 的 N 次方，使所有数值都变为整数，然后再用整数类型 01 背包问题求解。

#include <stdio.h>#include <string.h>int f[1000+10],w[1000+10],v[1000+10] ;int max(int x,int y){if(x>y) return x;else return y;}int main(){int t,m,i,j;memset(f,0,sizeof(f));scanf("%d %d",&t,&m);for (i=1;i<=m;i++) scanf("%d %d",&w[i],&v[i]);for (i=1;i<=m;i++){for (j=t;j>=w[i];j--){if(w[i]<=t)f[j]=max(f[j-w[i]]+v[i],f[j]);}}printf("%d",f[t]);printf(" ");}

int c[10][100];/*对应每种情况的最大价值*/int knapsack(int m,int n){ // 一个载重为m的背包 总共n个物品 int i,j,w[10],p[10]; printf("each weight & value ： "); for(i=1;i<=n;i++) scanf("%d %d",&w[i],&p[i]); // 第i个 物品的重量w[i] 价值p[i] for(i=0;i<10;i++) for(j=0;j<100;j++) c[i][j]=0;/*初始化数组*/ for(i=1;i<=n;i++) //遍历每一个物品i for(j=1;j<=m;j++) //假设背包的载重j为1、2、3、4、5、... ... m的情况 { if(j >= w[i]) /*如果当前物品的重量 < 背包载重*/ { if(p[i]+c[i-1][j-w[i]]>c[i-1][j])/*如果本物品的价值加上 背包剩下的空间能放的物品的价值 大于上一次选择的最佳方案则更新c[i][j]*/ c[i][j]=p[i]+c[i-1][j-w[i]]; else c[i][j]=c[i-1][j];// c[i][j] = (p[i]+c[i-1][j-w[i]]>c[i-1][j])?(p[i]+c[i-1][j-w[i]]):(c[i-1][j]); } else c[i][j]=c[i-1][j]; } return c[n][m];} int main(){ int m,n; printf("背包的承重量,物品的总个数： "); while(scanf("%d %d",&m,&n) != EOF){ printf("能装的最大总价值为%d",knapsack(m,n)); printf(" "); } return 0;}

using System;using System.Collections;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Text;using System.Windows.Forms;namespace Test01Bag{ public partial class Form1 : Form { public Form1() { InitializeComponent(); } public class Product { #region 商品类 /// <summary> /// 商品重量泛型List存储 /// </summary> private List<int> weight = new List<int>(); public List<int> Weight { get{ return weight; } set{ weight = value; } } private List<int> value = new List<int>(); /// <summary> /// 商品价值泛型List存储 /// </summary> public List<int> Value { get { return this.value; } set{ this.value = value; } } private int count; /// <summary> /// 商品数量 /// </summary> public int Count { get { count = weight.Count; return count; } } /// <summary> /// 添加商品信息 /// </summary> /// <param name="w">重量</param> /// <param name="v">价值</param> /// <returns></returns> public int setWeightAddValve(int w, int v) { weight.Add(w); value.Add(v); return weight.Count; } #endregion } public class Bag { #region 背包类 int[,] help = new int[100, 100]; int[] weight = new int[100]; int[] value = new int[100]; int count; int temp; // 背包容量 private int valume; public int Valume { get{ return valume; } set { valume = value; } } private int maxvalue; public int Maxvalue { get { return maxvalue; } set{ maxvalue = value; } } /// <summary> /// 设定容量temp暂存 /// </summary> /// <param name="v"></param> public void setValume(int v) { valume = v; temp = valume; } /// <summary> /// 引入数据 /// </summary> /// <param name="newprd">Product</param> public void setProduct(Product newprd) { count = newprd.Count; weight = newprd.Weight.ToArray(); value = newprd.Value.ToArray(); } /// <summary> /// 买商品 /// </summary> /// <returns></returns> public int buyproduct() { //初始化help表第一行为零 for (int w = 0; w < valume; w++) { help[0, w] = 0; } for (int i = 1; i <= count; i++) { // //初始化help表第一l列为零 help[i, 0] = 0; for (int w = 1; w <= valume; w++) { int temp = w - weight[i - 1]; if (weight[i - 1] <= w) { if (value[i - 1] + help[i - 1, temp] > help[i - 1, w]) { help[i, w] = value[i - 1] + help[i - 1, temp]; } else { help[i, w] = help[i - 1, w]; } } else { help[i, w] = help[i - 1, w]; } } } maxvalue = help[count, valume]; return maxvalue; } /// <summary> /// 显示结果买的商品状态存入ArrayList /// </summary> /// <returns></returns> public ArrayList showResult() { ArrayList result = new ArrayList(); if (weight[0] == help[1, temp]) { result.Add("Buy!"); } else { result.Add("Not Buy!"); } if (count >= 2) { for (int i = count; i <= 2; i--) { if (help[i, temp] == help[i - 1, temp]) { result.Add("Not Buy!"); } else { result.Add("Buy!"); } temp = temp - weight[i - 1]; } } return result; } #endregion } /// <summary> /// 实例化 /// </summary> Product newproduct = new Product(); Bag newbag = new Bag(); int i=1; private void Form1_Load(object sender, EventArgs e) { ///初始化 onit(); } public void onit() { #region 程序初始化 //清空 newproduct.Value.Clear(); newproduct.Weight.Clear(); newbag.Valume = 0; lstboxResult.Items.Clear(); #endregion } /// <summary> /// 存储商品信息函数 /// </summary> /// <param name="sender"></param> /// <param name="e"></param> private void btnAddProduct_Click(object sender, EventArgs e) { #region 添加商品信息 try { int w = Convert.ToInt32(txtWeight.Text); int v = Convert.ToInt32(txtValue.Text); newproduct.setWeightAddValve(w, v); i++; label1.Text = "请输入商品（" + i.ToString() + "）的体积："; label3.Text = "请输入商品（" + i.ToString() + "）的价值："; txtWeight.Text = ""; txtValue.Text = ""; } catch { MessageBox.Show("你的输入有错误，请重新输入！"); return; } #endregion } /// <summary> /// 问题解决函数 /// </summary> /// <param name="sender"></param> /// <param name="e"></param> private void btnToBuy_Click(object sender, EventArgs e) { #region 解决背包问题 try { int i = 1; int v = Convert.ToInt32(txtValume.Text); newbag.setValume(v); txtValume.Text = ""; newbag.setProduct(newproduct); int x = newbag.buyproduct(); lblMaxvalue.Text = "最大价值为：" + newbag.buyproduct().ToString(); ArrayList result = newbag.showResult(); int f = result.Count; foreach (string str in result) { string message = "商品" + i.ToString() + "--------" + str; lstboxResult.Items.Add(message); i++; } onit(); } catch { MessageBox.Show("你的输入有错误，请重新输入！"); return; } #endregion } }}

2.设计思想与分析：对物品的选取与否构成一棵解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。 #include <iostream.h> struct good{int weight; int benefit; int flag;//是否可以装入标记};int number=0;//物品数量 int upbound=0; int curp=0, curw=0;//当前效益值与重量 int maxweight=0; good *bag=NULL; void Init_good(){bag=new good [number]; for(int i=0; i<number; i++){cout<<"请输入第件"<<i+1<<"物品的重量:"; cin>>bag[i].weight; cout<<"请输入第件"<<i+1<<"物品的效益:"; cin>>bag[i].benefit; bag[i].flag=0;//初始标志为不装入背包 cout<<endl;}}int getbound(int num, int *bound_u)//返回本结点的c限界和u限界{for(int w=curw, p=curp; num<number && (w+bag[num].weight)<=maxweight; num++){w=w+bag[num].weight; p=w+bag[num].benefit;}*bound_u=p+bag[num].benefit; return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) );}void LCbag(){int bound_u=0, bound_c=0;//当前结点的c限界和u限界 for(int i=0; i<number; i++)//逐层遍历解树决定是否装入各个物品{if( ( bound_c=getbound(i+1, &bound_u) )>upbound )//遍历左子树 upbound=bound_u;//更改已有u限界,不更改标志 if( getbound(i, &bound_u)>bound_c )//遍历右子树 //若装入，判断右子树的c限界是否大于左子树根的c限界，是则装入{upbound=bound_u;//更改已有u限界 curp=curp+bag[i].benefit; curw=curw+bag[i].weight;//从已有重量和效益加上新物品 bag[i].flag=1;//标记为装入}}}void Display(){cout<<"可以放入背包的物品的编号为："; for(int i=0; i<number; i++) if(bag[i].flag>0) cout<<i+1<<" ";

贪心法是每一步的最优解就是整体的最优解。0-1背包是属于动态规划，每一步的解不一定导致整体的最优解。对于你问“什么样的题用0-1背包问题作”就是需要你自己做题来体会了。如果全局的最优解可以用分布的最优解求出来，就用贪心，如果不是，就动态规划（0-1背包属于这类）。合并果子问题（可以自己去网上找哈~）就是典型的贪心，0-1背包问题就属于典型动态规划。

1．0-1背包： 每个背包只能使用一次或有限次(可转化为一次)：A.求最多可放入的重量。NOIP2001 装箱问题 有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。l 搜索方法 procedure search(k,v:integer); var i,j:integer; begin if v<best then best:=v; if v-(s[n]-s[k-1])>=best then exit; if k<=n then begin if v>w[k] then search(k+1,v-w[k]); search(k+1,v); end; end;l DPF[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。实现:将最优化问题转化为判定性问题f [I, j] = f [ i-1, j-w[i] ] (w[I]<=j<=v) 边界：f[0,0]:=true.For I:=1 to n do For j:=w[I] to v do F[I,j]:=f[I-1,j-w[I]];优化：当前状态只与前一阶段状态有关，可降至一维。F[0]:=true;For I:=1 to n do begin F1:=f; For j:=w[I] to v doIf f[j-w[I]] then f1[j]:=true; F:=f1;End;B.求可以放入的最大价值。F[I,j] 为容量为I时取前j个背包所能获得的最大价值。F [i,j] = max C.求恰好装满的情况数。DP:Procedure update;var j,k:integer;begin c:=a; for j:=0 to n do if a[j]>0 then if j+now<=n then inc(c[j+now],a[j]); a:=c;end; 2．可重复背包A求最多可放入的重量。 F[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。状态转移方程为 f[I,j] = f [ I-1, j – w[I]*k ] (k=1.. j div w[I])B.求可以放入的最大价值。 USACO 1.2 Score Inflation 进行一次竞赛，总时间T固定，有若干种可选择的题目，每种题目可选入的数量不限，每种题目有一个ti（解答此题所需的时间）和一个si（解答此题所得的分数），现要选择若干题目，使解这些题的总时间在T以内的前提下，所得的总分最大，求最大的得分。 *易想到： f[i,j] = max (0<=k<= i div w[j])其中f[i,j]表示容量为i时取前j种背包所能达到的最大值。 *实现：Begin FillChar(f,SizeOf(f),0); For i:=1 To M Do For j:=1 To N Do If i-problem[j].time>=0 Then Begin t:=problem[j].point+f[i-problem[j].time]; If t>f[i] Then f[i]:=t; End; Writeln(f[M]);End.C.求恰好装满的情况数。Ahoi2001 Problem2求自然数n本质不同的质数和的表达式的数目。思路一，生成每个质数的系数的排列，在一一测试，这是通法。procedure try(dep:integer); var i,j:integer; begin cal; if now>n then exit; if dep=l+1 then begin cal; if now=n then inc(tot); exit; end; for i:=0 to n div pr[dep] do begin xs[dep]:=i; try(dep+1); xs[dep]:=0; end; end;思路二，递归搜索效率较高 procedure try(dep,rest:integer); var i,j,x:integer; begin if (rest<=0) or (dep=l+1) then begin if rest=0 then inc(tot); exit; end; for i:=0 to rest div pr[dep] do try(dep+1,rest-pr[dep]*i); end;思路三：可使用动态规划求解USACO1.2 money systemV个物品，背包容量为n，求放法总数。转移方程：Procedure update;var j,k:integer;begin c:=a; for j:=0 to n do if a[j]>0 then for k:=1 to n div now do if j+now*k<=n then inc(c[j+now*k],a[j]); a:=c;end;begin read(now); i:=0; while i<=n do begin a[i]:=1; inc(i,now); end; for i:=2 to v do begin read(now); update; end; writeln(a[n]);

最优解可能导致背包没装满。根据查询相关公开信息显示，动态规划动态规划先解决子问题，再逐步解决大问题。对于背包问题，你先解决小背包(子背包)问题，再逐步解决原来的问题。

　　背包问题是组合优化学科中一个经典而著名的问题，它的研究价值不言而喻，吸引了众多专家学者从各个角度开展对其的研究工作，各种算法设计思想也应运而生。由于背包问题的NP完全性，如何在算法的时间效率和求解精度上取得有效的平衡，成为背包问题算法设计主要的考虑因素。数据挖掘是近几年信息领域发展最快的技术之一。由于数据挖掘具有强大的发现有用知识的功能，可以利用它来发现背包问题解的相似的状态空间，然后进行约减，从而克服背包问题的NP困难性。　　背包问题，是用来介绍动态规划算法最经典的例子，网上关于01背包问题的讲解也很多，我写这篇文章力争做到用最简单的方式，最少的公式把01背包问题讲解透彻。　　01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }　　f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。　　Pi表示第i件物品的价值。　　决策：为了背包中物品总价值最大化，第 i件物品应该放入背包中吗 ？

对01背包求解，方法有回溯法、分支限界法、动态规划法等。给你一个较容易理解的解法：穷举搜索。问题求解的结果实际上是一个01序列，0表示该物品未装入背包，1表示装入背包。以本题为例，设求解结果为0111011，表示第0个和第4个未装入，其他均装入。关键就是如何找到这个01序列。设物品数量为n，则解空间为2^n，所以穷举搜索的时间效率为O(2^n)。#include <stdio.h>#define N 7int weight[N]={35, 30, 6, 50, 40 10, 25}, cost[N]={10, 40, 30, 50, 35, 40, 30};char name[] = "ABCDEFG";int max = 0, Max[N]; /*max用于存放最大价值，Max用于存放最优解向量*/int v[N]; /*v：求解时用于存放求解过程向量*/template <class T>void Swap(T &a, T &b){ T tmp = a; a = b, b = tmp;}void Knapsack(int step, int bag, int value1, int value2, int n)/*step表示第step步的选择（即第step个物品的选择），bag为背包剩余容量，value1表示包中现有物品总价值，value2表示剩余物品总价值，n为物品总数量*/{ int i; if((step >= n) || (weight[step] > bag) || (value1 + value2 <= max)) /*如果所有物品都选择完毕或剩余的物品都放不进或者包中物品总价值与剩余物品总价值之和小于等于目前的已知解，则找到一个解(但不一定是最终解或更优解)*/ { for(i = step; i < n; i++) v[i] = 0; /*剩余的物品都不放入*/ if(value1 > max) /*如果本次求得的解比以往的解更优，则将本次解作为更优解*/ { max = value1; for(i = 0; i < n; i++) Max[i] = v[i]; /*将更优解保存到Max向量中*/ } return; } v[step] = 0, Knapsack(step + 1, bag, value1, value2 - cost[step], n); /*不将第step个物品放入背包，第step个物品的价值被放弃，进行下一步的选择*/ v[step] = 1, Knapsack(step + 1, bag - weight[step], value1 + cost[step], value2 - cost[step], n); /*将第step个物品放入背包，进行下一步的选择*/}void main( ){ /*输入数据：背包容量、物品数量、重量、价值 代码略*/ int bag = 150, i, j, min, totalcost; /*按物品重量从小到大的顺序对物品排序，排序时cost向量中的相对顺序也要作相应移动*/ for(i = 0; i < N - 1; i++) { for(min = i, j = i + 1; j < N; j++) if(weight[j] < weight[min]) min = j; if(i != min) { Swap(weight[i], weight[min]); Swap(cost[i], cost[min]); Swap(name[i], name[min]); } } for(totalcost = 0, i = 0; i < N; i++) totalcost += cost[i]; /*求总价值*/ Knapsack(0, bag, 0, totalcost, N); /*bag为空背包容量, totalcost为物品总价值, N为物品数量*/ /*以下输出解*/ printf("最大价值为: %d。 装入背包的物品依次为： ", max); for(i = 0; i < N; i++) if(Max[i]) printf("%c ", name[i]); printf(" ");}我的回答你满意吗？如果满意，就请采纳哦，或者你也可以继续追问。

背包问题和0－1背包问题区别为：循环变量不同、约束条件不同、最大总价值不同。一、循环变量不同1、背包问题：背包问题须先求出列坐标j较小的元素，故让循环变量j的值从小到大递增。2、0－1背包问题：0－1背包问题须先求出列坐标j较大的元素，故让循环变量j的值从大到小递减。二、约束条件不同1、背包问题：背包问题的约束条件是给定几种物品，物品可以取无限次。2、0－1背包问题：0－1背包问题的约束条件是给定几种物品，物品只可以取一次。三、最大总价值不同1、背包问题：背包问题若取了1件第i个物品，则总容量变为j－W［i］，剩下的仍可以在前i件物品中去取，其最大总价值为B［i］［j－W［i］］ ＋ P［i］。2、0－1背包问题：0－1背包问题若取了1件第i个物品，则总容量变为j－W［i］，剩下的只能在前i－1件物品中去取了，其最大总价值为B［i－1］［j－W［i］］ ＋ P［i］。

算法分析　　　　对于背包问题，通常的处理方法是搜索。 　　用递归来完成搜索，算法设计如下： 　　function Make( i {处理到第i件物品} , j{剩余的空间为j}:integer) :integer; 　　初始时i=m , j=背包总容量 　　begin 　　if i:=0 then 　　Make:=0; 　　if j>=wi then (背包剩余空间可以放下物品 i ) 　　r1:=Make(i-1,j-wi)+v; (第i件物品放入所能得到的价值 ) 　　r2:=Make(i-1,j)　(第i件物品不放所能得到的价值 ) 　　Make:=max{r1,r2} 　　end; 　　这个算法的时间复杂度是O(2^n)，我们可以做一些简单的优化。 　　由于本题中的所有物品的体积均为整数，经过几次的选择后背包的剩余空间可能会相等，在搜索中会重复计算这些结点，所以，如果我们把搜索过程中计算过的结点的值记录下来，以保证不重复计算的话，速度就会提高很多。这是简单?quot;以空间换时间"。 　　我们发现，由于这些计算过程中会出现重叠的结点，符合动态规划中子问题重叠的性质。 　　同时，可以看出如果通过第N次选择得到的是一个最优解的话，那么第N-1次选择的结果一定也是一个最优解。这符合动态规划中最优子问题的性质。 　　考虑用动态规划的方法来解决，这里的： 　　 阶段是：在前N件物品中，选取若干件物品放入背包中； 　　状态是：在前N件物品中，选取若干件物品放入所剩空间为W的背包中的所能获得的最大价值； 　　 决策是：第N件物品放或者不放； 　　　由此可以写出动态转移方程： 　　我们用f[i,j]表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值 　　f[i,j]=max{f[i-1,j-Wi]+Pi (j>=Wi), f[i-1,j]} 　　这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c的背包中”，此时能获得的最大价值就是f[v-c]再加上通过放入第i件物品获得的价值w。　　　这样，我们可以自底向上地得出在前M件物品中取出若干件放进背包能获得的最大价值，也就是f[m,w] 　　算法设计如下：　　procedure Make; 　　begin 　　for i:=0 to w do 　　f[0,i]:=0; 　　for i:=1 to m do 　　for j:=0 to w do begin 　　f[i,j]:=f[i-1,j]; 　　if (j>=w) and (f[i-1,j-w]+v>f[i,j]) then 　　f[i,j]:=f[i-1,j-w]+v; 　　end; 　　writeln(f[m,wt]); 　　end; 　　由于是用了一个二重循环，这个算法的时间复杂度是O（n*w)。而用搜索的时候，当出现最坏的情况，也就是所有的结点都没有重叠，那么它的时间复杂度是O（2^n)。看上去前者要快很多。但是，可以发现在搜索中计算过的结点在动态规划中也全都要计算，而且这里算得更多（有一些在最后没有派上用场的结点我们也必须计算），在这一点上好像是矛盾的。 　　事实上，由于我们定下的前提是：所有的结点都没有重叠。也就是说，任意N件物品的重量相加都不能相等，而所有物品的重量又都是整数，那末这个时候W的最小值是：1+2+2^2+2^3+……+2^n-1=2^n -1 　　此时n*w>2^n，动态规划比搜索还要慢~~|||||||所以，其实背包的总容量W和重叠的结点的个数是有关的。 　　考虑能不能不计算那些多余的结点…… 　　 优化时间复杂度　　以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。　　先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[v]呢？f[v]是由f[v]和f[v-c]两个子问题递推而来，能否保证在推f[v]时（也即在第i次主循环中推f[v]时）能够得到f[v]和f[v-c]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c]保存的是状态f[v-c]的值。伪代码如下：　　for i=1..N　　for v=V..0　　f[v]=max{f[v],f[v-c]+w};　　其中的f[v]=max{f[v],f[v-c]}一句恰就相当于我们的转移方程f[v]=max{f[v],f[v-c]}，因为现在的f[v-c]就相当于原来的f[v-c]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[v]由f[v-c]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。　　事实上，使用一维数组解01背包的程序在后面会被多次用到，所以这里抽象出一个处理一件01背包中的物品过程，以后的代码中直接调用不加说明。　　过程ZeroOnePack，表示处理一件01背包中的物品，两个参数cost、weight分别表明这件物品的费用和价值。　　procedure ZeroOnePack(cost,weight)　　for v=V..cost　　f[v]=max{f[v],f[v-cost]+weight}　　注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成v=V..0是为了在程序中体现每个状态都按照方程求解了，避免不必要的思维复杂度。而这里既然已经抽象成看作黑箱的过程了，就可以加入优化。费用为cost的物品不会影响状态f[0..cost-1]，这是显然的。　　有了这个过程以后，01背包问题的伪代码就可以这样写：　　for i=1..N　　ZeroOnePack(c,w);　　 初始化的细节问题　　　　我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。　　如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。　　如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。　　为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。　　这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解

不知道你说的哪种类型的背包，我就说下最简单的吧。一、01背包问题描述：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。（1）基本思路：这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。意思简要来说就是：如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。（2）优化空间复杂度：以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下：for i=1..Nfor v=V..0f[v]=max{f[v],f[v-c[i]]+w[i]};其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符。（3）初始化的细节问题：我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。【写的伪代码，能看懂哈。。。不懂再问好了】

01背包问题就是有个容量为W的包，然后有一堆的物品(1...n)，其中wi、vi分别为第i个物品的重量和价值，现在需要求的就是使得包中所装的物品尽可能的价值高。那么这个物品放不放在包中对应取值0or1。其算法为动态规划，需要证明最优子结构性质。用s[i][j]表示只有前i个物品且包容量为j时所能等到的最大价值，而有递归式s[i][j]=s[i-1][j],wi>jmax{s[i-1][j],s[i-1][j-wi]+vi},wi<=js[0][j]=01<=j<=Ws[i][0]=01<=i<=n所以不论用什么语言实现，就是计算上面的式子，最终求得s[n][W]，上面的式子很好用递推实现的，这个是自底向上的，就是两层for；你也可以用栈实现自顶向下的，这个是记录式的方法。以上的W是只考虑整数的。

01背包问题的解空间树是一颗子集树。一般情况下，01背包问题是NP完全问题。01背包问题的解空间可以用子集树表示。解01背包问题的回溯法与解装载问题的回溯法十分相似。在搜索解空间树时，只要其左儿子节点是一个可行的就行。

P01: 01背包问题题目有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。优化空间复杂度以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下：for i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]};其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。事实上，使用一维数组解01背包的程序在后面会被多次用到，所以这里抽象出一个处理一件01背包中的物品过程，以后的代码中直接调用不加说明。过程ZeroOnePack，表示处理一件01背包中的物品，两个参数cost、weight分别表明这件物品的费用和价值。procedure ZeroOnePack(cost,weight) for v=V..cost f[v]=max{f[v],f[v-cost]+weight}注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成v=V..0是为了在程序中体现每个状态都按照方程求解了，避免不必要的思维复杂度。而这里既然已经抽象成看作黑箱的过程了，就可以加入优化。费用为cost的物品不会影响状态f[0..cost-1]，这是显然的。有了这个过程以后，01背包问题的伪代码就可以这样写：for i=1..N ZeroOnePack(c[i],w[i]);初始化的细节问题我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解。小结01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。

背包问题 它是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人拥有大量物品，重量各不同。此人通过秘密地选择一部分物品并将它们放到背包中来加密消息。背包中的物品中重量是公开的，所有可能的物品也是公开的，但背包中的物品是保密的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。但是，大多数一次背包体制均被破译了，因此现在很少有人使用它。 DD牛的背包九讲 P01: 01背包问题 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c，价值是w。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 基本思路 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即f[v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[v]=max{f[v],f[v-c]+w}。 这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c的背包中”，此时能获得的最大价值就是f [v-c]再加上通过放入第i件物品获得的价值w。 注意f[v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，最终的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项f[v-1]，这样就可以保证f[N] [V]就是最后的答案。至于为什么这样就可以，由你自己来体会了。 优化空间复杂度 以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。 先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[0..V]的所有值。那么，如果只用一个数组f [0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[v]呢？f[v]是由f[v]和f [v-c]两个子问题递推而来，能否保证在推f[v]时（也即在第i次主循环中推f[v]时）能够得到f[v]和f[v -c]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c]保存的是状态f[v-c]的值。伪代码如下： for i=1..N for v=V..0 f[v]=max{f[v],f[v-c]+w}; 其中的f[v]=max{f[v],f[v-c]}一句恰就相当于我们的转移方程f[v]=max{f[v],f[v-c]}，因为现在的f[v-c]就相当于原来的f[v-c]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[v]由f[v-c]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。 总结 01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。 P02: 完全背包问题 题目 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c，价值是w。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 基本思路 这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令f[v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：f[v]=max{f[v-k*c]+k*w|0<=k*c<= v}。这跟01背包问题一样有O(N*V)个状态需要求解，但求解每个状态的时间则不是常数了，求解状态f[v]的时间是O(v/c)，总的复杂度是超过O(VN)的。 将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。 一个简单有效的优化 完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足c<=c[j]且w>=w[j]，则将物品j去掉，不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高得j换成物美价廉的i，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。 转化为01背包问题求解 既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是，考虑到第i种物品最多选V/c 件，于是可以把第i种物品转化为V/c件费用及价值均不变的物品，然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。 更高效的转化方法是：把第i种物品拆成费用为c*2^k、价值为w*2^k的若干件物品，其中k满足c*2^k<V。这是二进制的思想，因为不管最优策略选几件第i种物品，总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log(V/c))件物品，是一个很大的改进。 但我们有更优的O(VN)的算法。 * O(VN)的算法 这个算法使用一维数组，先看伪代码： <pre class"example"> for i=1..N for v=0..V f[v]=max{f[v],f[v-c]+w}; 你会发现，这个伪代码与P01的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢？首先想想为什么P01中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[v]是由状态f[v-c]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[v-c]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[v-c]，所以就可以并且必须采用v= 0..V的顺序循环。这就是这个简单的程序为何成立的道理。 这个算法也可以以另外的思路得出。例如，基本思路中的状态转移方程可以等价地变形成这种形式：f[v]=max{f[v],f[v-c]+w}，将这个方程用一维数组实现，便得到了上面的伪代码。 总结 完全背包问题也是一个相当基础的背包问题，它有两个状态转移方程，分别在“基本思路”以及“O(VN)的算法“的小节中给出。希望你能够对这两个状态转移方程都仔细地体会，不仅记住，也要弄明白它们是怎么得出来的，最好能够自己想一种得到这些方程的方法。事实上，对每一道动态规划题目都思考其方程的意义以及如何得来，是加深对动态规划的理解、提高动态规划功力的好方法。 P03: 多重背包问题 题目 有N种物品和一个容量为V的背包。第i种物品最多有n件可用，每件费用是c，价值是w。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 基本算法 这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n+1种策略：取0件，取1件……取 n件。令f[v]表示前i种物品恰放入一个容量为v的背包的最大权值，则：f[v]=max{f[v-k*c]+ k*w|0<=k<=n}。复杂度是O(V*∑n)。 转化为01背包问题 另一种好想好写的基本方法是转化为01背包求解：把第i种物品换成n件01背包中的物品，则得到了物品数为∑n的01背包问题，直接求解，复杂度仍然是O(V*∑n)。 但是我们期望将它转化为01背包问题之后能够像完全背包一样降低复杂度。仍然考虑二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略——取0..n件——均能等价于取若干件代换以后的物品。另外，取超过n件的策略必不能出现。 方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为 1,2,4,...,2^(k-1),n-2^k+1，且k是满足n-2^k+1>0的最大整数。例如，如果n为13，就将这种物品分成系数分别为1,2,4,6的四件物品。 分成的这几件物品的系数和为n，表明不可能取多于n件的第i种物品。另外这种方法也能保证对于0..n间的每一个整数，均可以用若干个系数的和表示，这个证明可以分0..2^k-1和2^k..n两段来分别讨论得出，并不难，希望你自己思考尝试一下。 这样就将第i种物品分成了O(log n)种物品，将原问题转化为了复杂度为O(V*∑log n)的01背包问题，是很大的改进。 O(VN)的算法 多重背包问题同样有O(VN)的算法。这个算法基于基本算法的状态转移方程，但应用单调队列的方法使每个状态的值可以以均摊O(1)的时间求解。由于用单调队列优化的DP已超出了NOIP的范围，故本文不再展开讲解。我最初了解到这个方法是在楼天成的“男人八题”幻灯片上。 小结 这里我们看到了将一个算法的复杂度由O(V*∑n)改进到O(V*∑log n)的过程，还知道了存在应用超出NOIP范围的知识的O(VN)算法。希望你特别注意“拆分物品”的思想和方法，自己证明一下它的正确性，并用尽量简洁的程序来实现。 P04: 混合三种背包问题 问题 如果将P01、P02、P03混合起来。也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。应该怎么求解呢？ 01背包与完全背包的混合 考虑到在P01和P02中最后给出的伪代码只有一处不同，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可，复杂度是O(VN)。伪代码如下： for i=1..N if 第i件物品是01背包 for v=V..0 f[v]=max{f[v],f[v-c]+w}; else if 第i件物品是完全背包 for v=0..V f[v]=max{f[v],f[v-c]+w}; 再加上多重背包 如果再加上有的物品最多可以取有限次，那么原则上也可以给出O(VN)的解法：遇到多重背包类型的物品用单调队列解即可。但如果不考虑超过NOIP范围的算法的话，用P03中将每个这类物品分成O(log n)个01背包的物品的方法也已经很优了。 小结 有人说，困难的题目都是由简单的题目叠加而来的。这句话是否公理暂且存之不论，但它在本讲中已经得到了充分的体现。本来01背包、完全背包、多重背包都不是什么难题，但将它们简单地组合起来以后就得到了这样一道一定能吓倒不少人的题目。但只要基础扎实，领会三种基本背包问题的思想，就可以做到把困难的题目拆分成简单的题目来解决。 P05: 二维费用的背包问题 问题 二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a和b。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w。 算法 费用加了一维，只需状态也加一维即可。设f[v]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。状态转移方程就是：f [v]=max{f[v],f[v-a]]+w}。如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量v和u采用顺序的循环，当物品有如完全背包问题时采用逆序的循环。当物品有如多重背包问题时拆分物品。 物品总个数的限制 有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取M件物品。这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为1，可以付出的最大件数费用为M。换句话说，设f[v][m]表示付出费用v、最多选m件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，最后在f[0..V][0..M]范围内寻找答案。 另外，如果要求“恰取M件物品”，则在f[0..V][M]范围内寻找答案。 小结 事实上，当发现由熟悉的动态规划题目变形得来的题目时，在原来的状态中加一纬以满足新的限制是一种比较通用的方法。希望你能从本讲中初步体会到这种方法。 P06: 分组的背包问题 问题 有N件物品和一个容量为V的背包。第i件物品的费用是c，价值是w。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 算法 这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有f[k][v]=max{f[k-1][v],f[k-1][v-c]+w|物品i属于第k组}。 使用一维数组的伪代码如下： for 所有的组k for 所有的i属于组k for v=V..0 f[v]=max{f[v],f[v-c]+w} 另外，显然可以对每组中的物品应用P02中“一个简单有效的优化”。 小结 分组的背包问题将彼此互斥的若干物品称为一个组，这建立了一个很好的模型。不少背包问题的变形都可以转化为分组的背包问题（例如P07），由分组的背包问题进一步可定义“泛化物品”的概念，十分有利于解题。 P07: 有依赖的背包问题 简化的问题 这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。 算法 这个问题由NOIP2006金明的预算方案一题扩展而来。遵从该题的提法，将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的一个附件集合组成。 按照背包问题的一般思路，仅考虑一个主件和它的附件集合。可是，可用的策略非常多，包括：一个也不选，仅选择主件，选择主件后再选择一个附件，选择主件后再选择两个附件……无法用状态转移方程来表示如此多的策略。（事实上，设有n个附件，则策略有2^n+1个，为指数级。） 考虑到所有这些策略都是互斥的（也就是说，你只能选择一种策略），所以一个主件和它的附件集合实际上对应于P06中的一个物品组，每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品，其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法，因为物品组中的物品还是像原问题的策略一样多。 再考虑P06中的一句话： 可以对每组中的物品应用P02中“一个简单有效的优化”。这提示我们，对于一个物品组中的物品，所有费用相同的物品只留一个价值最大的，不影响结果。所以，我们可以对主件i的“附件集合”先进行一次01背包，得到费用依次为0..V-c所有这些值时相应的最大价值f"[0..V-c]。那么这个主件及它的附件集合相当于V-c+1个物品的物品组，其中费用为c+k的物品的价值为f"[k]+w。也就是说原来指数级的策略中有很多策略都是冗余的，通过一次01背包后，将主件i转化为 V-c+1个物品的物品组，就可以直接应用P06的算法解决问题了。 更一般的问题 更一般的问题是：依赖关系以图论中“森林”的形式给出（森林即多叉树的集合），也就是说，主件的附件仍然可以具有自己的附件集合，限制只是每个物品最多只依赖于一个物品（只有一个主件）且不出现循环依赖。 解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是，由于附件可能还有附件，就不能将每个附件都看作一个一般的01 背包中的物品了。若这个附件也有附件集合，则它必定要被先转化为物品组，然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。 事实上，这是一种树形DP，其特点是每个父节点都需要对它的各个儿子的属性进行一次DP以求得自己的相关属性。这已经触及到了“泛化物品”的思想。看完P08后，你会发现这个“依赖关系树”每一个子树都等价于一件泛化物品，求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。 P08: 泛化物品 定义 考虑这样一种物品，它并没有固定的费用和价值，而是它的价值随着你分配给它的费用而变化。这就是泛化物品的概念。 更严格的定义之。在背包容量为V的背包问题中，泛化物品是一个定义域为0..V中的整数的函数h，当分配给它的费用为v时，能得到的价值就是h(v)。 这个定义有一点点抽象，另一种理解是一个泛化物品就是一个数组h[0..V]，给它费用v，可得到价值h[V]。 一个费用为c价值为w的物品，如果它是01背包中的物品，那么把它看成泛化物品，它就是除了h(c)=w其它函数值都为0的一个函数。如果它是完全背包中的物品，那么它可以看成这样一个函数，仅当v被c整除时有h(v)=v/c*w，其它函数值均为0。如果它是多重背包中重复次数最多为n的物品，那么它对应的泛化物品的函数有h(v)=v/c*w仅当v被c整除且v/c<=n，其它情况函数值均为0。 一个物品组可以看作一个泛化物品h。对于一个0..V中的v，若物品组中不存在费用为v的的物品，则h(v)=0，否则h(v)为所有费用为v的物品的最大价值。P07中每个主件及其附件集合等价于一个物品组，自然也可看作一个泛化物品。 泛化物品的和 如果面对两个泛化物品h和l，要用给定的费用从这两个泛化物品中得到最大的价值，怎么求呢？事实上，对于一个给定的费用v，只需枚举将这个费用如何分配给两个泛化物品就可以了。同样的，对于0..V的每一个整数v，可以求得费用v分配到h和l中的最大价值f(v)。也即f(v)=max{h(k) +l(v-k)|0<=k<=v}。可以看到，f也是一个由泛化物品h和l决定的定义域为0..V的函数，也就是说，f是一个由泛化物品h和 l决定的泛化物品。 由此可以定义泛化物品的和：h、l都是泛化物品，若泛化物品f满足f(v)=max{h(k)+l(v-k)|0<=k<=v}，则称f是h与l的和，即f=h+l。这个运算的时间复杂度是O(V^2)。 泛化物品的定义表明：在一个背包问题中，若将两个泛化物品代以它们的和，不影响问题的答案。事实上，对于其中的物品都是泛化物品的背包问题，求它的答案的过程也就是求所有这些泛化物品之和的过程。设此和为s，则答案就是s[0..V]中的最大值。 背包问题的泛化物品 一个背包问题中，可能会给出很多条件，包括每种物品的费用、价值等属性，物品之间的分组、依赖等关系等。但肯定能将问题对应于某个泛化物品。也就是说，给定了所有条件以后，就可以对每个非负整数v求得：若背包容量为v，将物品装入背包可得到的最大价值是多少，这可以认为是定义在非负整数集上的一件泛化物品。这个泛化物品——或者说问题所对应的一个定义域为非负整数的函数——包含了关于问题本身的高度浓缩的信息。一般而言，求得这个泛化物品的一个子域（例如0..V）的值之后，就可以根据这个函数的取值得到背包问题的最终答案。 综上所述，一般而言，求解背包问题，即求解这个问题所对应的一个函数，即该问题的泛化物品。而求解某个泛化物品的一种方法就是将它表示为若干泛化物品的和然后求之。 小结 本讲可以说都是我自己的原创思想。具体来说，是我在学习函数式编程的 Scheme 语言时，用函数编程的眼光审视各类背包问题得出的理论。这一讲真的很抽象，也许在“模型的抽象程度”这一方面已经超出了NOIP的要求，所以暂且看不懂也没关系。相信随着你的OI之路逐渐延伸，有一天你会理解的。 我想说：“思考”是一个OIer最重要的品质。简单的问题，深入思考以后，也能发现更多。 P09: 背包问题问法的变化 以上涉及的各种背包问题都是要求在背包容量（费用）的限制下求可以取到的最大价值，但背包问题还有很多种灵活的问法，在这里值得提一下。但是我认为，只要深入理解了求背包问题最大价值的方法，即使问法变化了，也是不难想出算法的。 例如，求解最多可以放多少件物品或者最多可以装满多少背包的空间。这都可以根据具体问题利用前面的方程求出所有状态的值（f数组）之后得到。 还有，如果要求的是“总价值最小”“总件数最小”，只需简单的将上面的状态转移方程中的max改成min即可。 下面说一些变化更大的问法。 输出方案 一般而言，背包问题是要求一个最优值，如果要求输出这个最优值的方案，可以参照一般动态规划问题输出方案的方法：记录下每个状态的最优值是由状态转移方程的哪一项推出来的，换句话说，记录下它是由哪一个策略推出来的。便可根据这条策略找到上一个状态，从上一个状态接着向前推即可。 还是以01背包为例，方程为f[v]=max{f[v],f[v-c]+w}。再用一个数组g [v]，设g[v]=0表示推出f[v]的值时是采用了方程的前一项（也即f[v]=f[v]），g[v]表示采用了方程的后一项。注意这两项分别表示了两种策略：未选第i个物品及选了第i个物品。那么输出方案的伪代码可以这样写（设最终状态为f[N][V]）： i=N v=V while(i>0) if(g[v]==0) print "未选第i项物品" else if(g[v]==1) print "选了第i项物品" v=v-c 另外，采用方程的前一项或后一项也可以在输出方案的过程中根据f[v]的值实时地求出来，也即不须纪录g数组，将上述代码中的g [v]==0改成f[v]==f[v]，g[v]==1改成f[v]==f[v-c]+w也可。 输出字典序最小的最优方案 这里“字典序最小”的意思是1..N号物品的选择方案排列出来以后字典序最小。以输出01背包最小字典序的方案为例。 一般而言，求一个字典序最小的最优方案，只需要在转移时注意策略。首先，子问题的定义要略改一些。我们注意到，如果存在一个选了物品1的最优方案，那么答案一定包含物品1，原问题转化为一个背包容量为v-c[1]，物品为2..N的子问题。反之，如果答案不包含物品1，则转化成背包容量仍为V，物品为2..N的子问题。不管答案怎样，子问题的物品都是以i..N而非前所述的1..i的形式来定义的，所以状态的定义和转移方程都需要改一下。但也许更简易的方法是先把物品逆序排列一下，以下按物品已被逆序排列来叙述。 在这种情况下，可以按照前面经典的状态转移方程来求值，只是输出方案的时候要注意：从N到1输入时，如果f[v]==f及f[v]==f[f-c]+w同时成立，应该按照后者（即选择了物品i）来输出方案。 求方案总数 对于一个给定了背包容量、物品费用、物品间相互关系（分组、依赖等）的背包问题，除了再给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。 对于这类改变问法的问题，一般只需将状态转移方程中的max改成sum即可。例如若每件物品均是01背包中的物品，转移方程即为f[v]=sum{f[v],f[v-c]+w}，初始条件f[0][0]=1。 事实上，这样做可行的原因在于状态转移方程已经考察了所有可能的背包组成方案。 最优方案的总数 这里的最优方案是指物品总价值最大的方案。还是以01背包为例。 结合求最大总价值和方案总数两个问题的思路，最优方案的总数可以这样求：f[v]意义同前述，g[v]表示这个子问题的最优方案的总数，则在求f[v]的同时求g[v]的伪代码如下： for i=1..N for v=0..V f[v]=max{f[v],f[v-c]+w} g[v]=0 if(f[v]==f[v]) inc(g[v],g[v] if(f[v]==f[v-c]+w) inc(g[v],g[v-c]) 如果你是第一次看到这样的问题，请仔细体会上面的伪代码。 小结 显然，这里不可能穷尽背包类动态规划问题所有的问法。甚至还存在一类将背包类动态规划问题与其它领域（例如数论、图论）结合起来的问题，在这篇论背包问题的专文中也不会论及。但只要深刻领会前述所有类别的背包问题的思路和状态转移方程，遇到其它的变形问法，只要题目难度还属于NOIP，应该也不难想出算法。 触类旁通、举一反三，应该也是一个OIer应有的品质吧。