01背包问题

01背包问题Postedon2009-06-1115:55YDN阅读(673)评论(4)编辑收藏所属分类:动态规划问题描述：有n件物品x1,x2,…,xn,每件物品有一个价值和一个重量，分别记为：v1,v2,…vnw1,w2,…wn其中所有的wi均为整数。现有一个背包，其最大载重量为m，要求从这n件物品中任取若干件（这些物品每样只有一件，要么被装入要么被留下）。问背包中装入哪些物品可使得所装物品的价值和最大？（我们只需要求出最大价值，不需要求出具体拿的是哪些物品）例如，m=23,n=5,vi:1924334550wi:5681112最大价值为：95分析：如果想用贪心，先求出平均价值，然后从高到低的方法来取，如果有一个背包的容量为10，共有3个物品，体积分别是3、3、5，价值分别是6、6、9，那么你的方法取到的是前两个物品，总价值是12，但明显最大值是后两个物品组成的15。因此贪心的方法不能得到正确结果。换一个更简单的方式来思考：每个物品只有2种选择，要么放入，要么不放入。（1）放入：问题转换为在背包载重为m-wi的情况下，在其它n-1件物品中挑选，求得价值和最大。等把这个子问题求出后，再加上vi的价值就是整个问题的最优解了。（2）没放入：那么就当xi根本不存在，直接解物品数量为n-1，背包载重为m的子问题。子问题的最优解就是问题的最优解。定义函数f(i,j)为在1~i件物品中选若干件装入限重为j的背包中的最大价值和，那么根据上面关于第i件物品是否装入了背包的情况分析，我们得出关系式：(1)当第I件物品要装入背包时，f(i,j):=(i-1件物品，限重为j-w[i]的最优解)+v[i],即：f(i,j):=f(i-1,j-w[i])+v[i]当然，第i件物品要装入是有条件限制的：第i件物品重量小于等于背包限重，即w[i]=j（2）当第i件物品不装入背包时，f(i,j):=i-1件物品，限重为m的最优解，即：f(i,j):=f(i-1,j)求得装入或者不装入第i件物品的限重为J的背包的最大价值，只需要比较这两种情况下谁的价值更大，更大者为当前问题的最优解。f(i,j)=max{f(i-1,j-w[i])+v[i],f(i-1,j)}该方程递归结束的边界条件是：当j=0时，f(i,0)=0。在按自底向上的动态规划方式求解问题时，其实主要就是做一件事：按问题规模从小到大地求解问题，把每阶段求得的问题的最优解保存在表格（数组）中，以便在下一阶段求解更大的问题时，可以直接查表引用子问题的最优解。（类似于递推）阶段的分析：将n件物品放入背包，故可以把阶段划分为n个。把在前I件物品中选取物品放入背包作为第I个阶段。状态的分析：在第i个阶段有多少个状态呢?因为包的容量为m，故在每个i阶段都有m个状态：f(i,1)、f(i,2)、f(i,3)……f(i,m-1)、f(i,m)。而这m个问题的求解基础是第I-1个阶段的m个子问题。这些子问题的最优解已经先于此时求得，保存在f[I-1,1],f[I-1,2],…,f[I-1,m]中，现在只需要直接引用它们的值就可以了。这就是动态规划自底向上的体现。之所以能求得之前的状态，是因为有一个边界：f(i,0)=0。决策的分析：只有两个，在前I件物品中，限重为J的条件下，装入第I件物品还是不装入第I件物品。比较这两种情况的价值和，谁大谁就是最优解。1//01背包问题2programbeibao01;3var4v,w:array[1..100]ofinteger;//物品的价值和重量5f:array[0..1000,0..1000]ofinteger;//取得的价值6m,n,i,j:integer;//m为包的容量，n为物品数78procedureinit;9begin10readln(m,n);11fori:=1tondo12read(w[i],v[i]);13end;1415procedurework;16begin17fori:=1tondo//阶段18forj:=1tomdo//状态19if(j=w[i])then//如果包的容量还能够放下一个包20if(f[i-1,j-w[i]]+v[i])f[i-1,j]then//比较不放包和放包两中策略中价值大的一种21f[i,j]:=f[i-1,j-w[i]]+v[i]//能放时候的价值22else23f[i,j]:=f[i-1,j];//不能放时候的价值24end;2526begin27init;28work;29writeln(f[n,m]);30readln;31end.