01背包问题论文.docVIP

0-1背包问题 问题描述 给定n个物品和一个背包，物品i的重量为wi，价值为vi（i=1,2,……,n），背包能容纳的物品的重量为c，要从这n个物品中选出若干件放入背包，使得放入物品的总重量不超过c，而总价值达到最大，并找出一种放物品的方案。 输入 输入有若干组测试数据(不超过20组)。 每组测试数据有3行：其第1行上有2个整数n和c，分别是物品个数n和背包所能容纳物品的重量，（n=50,c=500），第2行上有n个整数v1、v2、…、vn，依次是n个物品的价值，第3行上有n个整数w1、w2、…、wn,，分别是n个物品的重量。诸整数之间用一个空格分开。 输出 现要求对输入中的每组测试数据，输出2行：在第1行上输出“Case #”，其中“#”是测试数据的组号（从1开始）。在第2行上输出具体放物品的结果：首先输出一个整数bestv及一个由0或1构成的字符串x1x2…xn，其中bestv表示物品可以放在包中的最大价值，x1x2…xn是对应于bestv的具体放包方案，xi=1表示第i个物品放入包中，而xi=0表示第i个物品不放入包中。 对应于bestv的具体放包方案可能不唯一，如价值分别为1、3、4，重量分别为3、1、4的物品放如能承重4的包中，那么有装载方案110和001两种。为使输出结果可操作，我们约定长为n的0-1字符串以字典序最小的那个为符合要求的装包方案。 输入样例 3 4 1 3 4 3 1 4 5 10 6 3 5 4 6 2 2 6 5 4 输出样例 Case 1 4 001 Case 2 15 11001 解决0/1背包问题的方法有多种，最常用的有贪婪法和动态规划法。其中贪婪法无法得到问题的最优解，而动态规划法都可以得到最优解，下面是用动态规划法来解决0/1背包问题。 动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的，若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费过多的时间。动态规划法又和贪婪算法有些一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。 在0 / 1背包问题中，需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即p1*x1+p2*x1+...+pi*xi(其1=i=n，x取0或1，取1表示选取物品i) 取得最大值。 在该问题中需要决定x1 .. xn的值。假设按i = 1，2，...，n 的次序来确定xi 的值。如果置x1 = 0，则问题转变为相对于其余物品(即物品2，3，.，n)，背包容量仍为c 的背包问题。若置x1 = 1，问题就变为关于最大背包容量为c-w1 的问题。现设r?{c，c-w1 } 为剩余的背包容量。 在第一次决策之后，剩下的问题便是考虑背包容量为r 时的决策。不管x1 是0或是1，[x2 ，.，xn ] 必须是第一次决策之后的一个最优方案，如果不是，则会有一个更好的方案[y2，.，yn ]，因而[x1，y2，.，yn ]是一个更好的方案。 假设n=3, w=[100,14,10], p=[20,18,15], c= 116。若设x1 = 1，则在本次决策之后，可用的背包容量为r= 116-100=16 。[x2，x3 ]=[0,1] 符合容量限制的条件，所得值为1 5，但因为[x2，x3 ]= [1，0] 同样符合容量条件且所得值为1 8，因此[x2，x3 ] = [ 0，1] 并非最优策略。即x= [ 1，0，1] 可改进为x= [ 1，1，0 ]。若设x1 = 0，则对于剩下的两种物品而言，容量限制条件为116。总之，如果子问题的结果[x2，x3 ]不是剩余情况下的一个最优解，则[x1，x2，x3 ]也不会是总体的最优解。在此问题中，最优决策序列由最优决策子序列组成。假设f (i,y) 表示剩余容量为y，剩余物品为i，i + 1，...，n 时的最优解的值，即：利用最优序列由最优子序列构成的结论，可得到f 的递归式为： 当j=wi时： f(i,j)=max{f(i+1,j),f(i+1,j-wi)+vi} ①式 当0=jwi时：f(i,j)=f(i+1,j) ②式 fn( 1 ,c) 是初始时背包问题的最优解。 以本题为例：若0≤y＜1 0，则f ( 3 ,y) = 0；若y≥1 0，f ( 3 ,y