0_1背包问题
- 格式:pptx
- 大小:846.62 KB
- 文档页数:6
贪⼼算法-01背包问题1、问题描述:给定n种物品和⼀背包。
物品i的重量是wi,其价值为vi,背包的容量为C。
问:应如何选择装⼊背包的物品,使得装⼊背包中物品的总价值最⼤?形式化描述:给定c >0, wi >0, vi >0 , 1≤i≤n.要求找⼀n元向量(x1,x2,…,xn,), xi∈{0,1}, ∋ ∑ wi xi≤c,且∑ vi xi达最⼤.即⼀个特殊的整数规划问题。
2、最优性原理:设(y1,y2,…,yn)是 (3.4.1)的⼀个最优解.则(y2,…,yn)是下⾯相应⼦问题的⼀个最优解:证明:使⽤反证法。
若不然,设(z2,z3,…,zn)是上述⼦问题的⼀个最优解,⽽(y2,y3,…,yn)不是它的最优解。
显然有∑vizi > ∑viyi (i=2,…,n)且 w1y1+ ∑wizi<= c因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n)说明(y1,z2, z3,…,zn)是(3.4.1)0-1背包问题的⼀个更优解,导出(y1,y2,…,yn)不是背包问题的最优解,⽭盾。
3、递推关系:设所给0-1背包问题的⼦问题的最优值为m(i,j),即m(i,j)是背包容量为j,可选择物品为i,i+1,…,n时0-1背包问题的最优值。
由0-1背包问题的最优⼦结构性质,可以建⽴计算m(i,j)的递归式:注:(3.4.3)式此时背包容量为j,可选择物品为i。
此时在对xi作出决策之后,问题处于两种状态之⼀:(1)背包剩余容量是j,没产⽣任何效益;(2)剩余容量j-wi,效益值增长了vi ;使⽤递归C++代码如下:#include<iostream>using namespace std;const int N=3;const int W=50;int weights[N+1]={0,10,20,30};int values[N+1]={0,60,100,120};int V[N+1][W+1]={0};int knapsack(int i,int j){int value;if(V[i][j]<0){if(j<weights[i]){value=knapsack(i-1,j);}else{value=max(knapsack(i-1,j),values[i]+knapsack(i-1,j-weights[i]));}V[i][j]=value;}return V[i][j];}int main(){int i,j;for(i=1;i<=N;i++)for(j=1;j<=W;j++)V[i][j]=-1;cout<<knapsack(3,50)<<endl;cout<<endl;}不使⽤递归的C++代码:简单⼀点的修改//3d10-1 动态规划背包问题#include <iostream>using namespace std;const int N = 4;void Knapsack(int v[],int w[],int c,int n,int m[][10]);void Traceback(int m[][10],int w[],int c,int n,int x[]);int main(){int c=8;int v[]={0,2,1,4,3},w[]={0,1,4,2,3};//下标从1开始int x[N+1];int m[10][10];cout<<"待装物品重量分别为:"<<endl;for(int i=1; i<=N; i++){cout<<w[i]<<" ";}cout<<endl;cout<<"待装物品价值分别为:"<<endl;for(int i=1; i<=N; i++){cout<<v[i]<<" ";}cout<<endl;Knapsack(v,w,c,N,m);cout<<"背包能装的最⼤价值为:"<<m[1][c]<<endl;Traceback(m,w,c,N,x);cout<<"背包装下的物品编号为:"<<endl;for(int i=1; i<=N; i++){if(x[i]==1){cout<<i<<" ";}}cout<<endl;return 0;}void Knapsack(int v[],int w[],int c,int n,int m[][10]){int jMax = min(w[n]-1,c);//背包剩余容量上限范围[0~w[n]-1] for(int j=0; j<=jMax;j++){m[n][j]=0;}for(int j=w[n]; j<=c; j++)//限制范围[w[n]~c]{m[n][j] = v[n];}for(int i=n-1; i>1; i--){jMax = min(w[i]-1,c);for(int j=0; j<=jMax; j++)//背包不同剩余容量j<=jMax<c{m[i][j] = m[i+1][j];//没产⽣任何效益}for(int j=w[i]; j<=c; j++) //背包不同剩余容量j-wi >c{m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]);//效益值增长vi }}m[1][c] = m[2][c];if(c>=w[1]){m[1][c] = max(m[1][c],m[2][c-w[1]]+v[1]);}}//x[]数组存储对应物品0-1向量,0不装⼊背包,1表⽰装⼊背包void Traceback(int m[][10],int w[],int c,int n,int x[]){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])?1:0;}运⾏结果:算法执⾏过程对m[][]填表及Traceback回溯过程如图所⽰:从m(i,j)的递归式容易看出,算法Knapsack需要O(nc)计算时间; Traceback需O(n)计算时间;算法总体需要O(nc)计算时间。
动态规划——01背包问题⼀、最基础的动态规划之⼀01背包问题是动态规划中最基础的问题之⼀,它的解法完美地体现了动态规划的思想和性质。
01背包问题最常见的问题形式是:给定n件物品的体积和价值,将他们尽可能地放⼊⼀个体积固定的背包,最⼤的价值可以是多少。
我们可以⽤费⽤c和价值v来描述⼀件物品,再设允许的最⼤花费为w。
只要n稍⼤,我们就不可能通过搜索来遍查所有组合的可能。
运⽤动态规划的思想,我们把原来的问题拆分为⼦问题,⼦问题再进⼀步拆分直⾄不可再分(初始值),随后从初始值开始,尽可能地求取每⼀个⼦问题的最优解,最终就能求得原问题的解。
由于不同的问题可能有相同的⼦问题,⼦问题存在⼤量重叠,我们需要额外的空间来存储已经求得的⼦问题的最优解。
这样,可以⼤幅度地降低时间复杂度。
有了这样的思想,我们来看01背包问题可以怎样拆分成⼦问题:要求解的问题是:在n件物品中最⼤花费为w能得到的最⼤价值。
显然,对于0 <= i <= n,0 <= j <= w,在前i件物品中最⼤花费为j能得到的最⼤价值。
可以使⽤数组dp[n + 1][w + 1]来存储所有的⼦问题,dp[i][j]就代表从前i件物品中选出总花费不超过j时的最⼤价值。
可知dp[0][j]值⼀定为零。
那么,该怎么递推求取所有⼦问题的解呢。
显⽽易见,要考虑在前i件物品中拿取,⾸先要考虑前i - 1件物品中拿取的最优情况。
当我们从第i - 1件物品递推到第i件时,我们就要考虑这件物品是拿,还是不拿,怎样收益最⼤。
①:⾸先,如果j < c[i],那第i件物品是⽆论如何拿不了的,dp[i][j] = dp[i - 1][j];②:如果可以拿,那就要考虑拿了之后收益是否更⼤。
拿这件物品需要花费c[i],除去这c[i]的⼦问题应该是dp[i - 1][j - c[i]],这时,就要⽐较dp[i - 1][j]和dp[i - 1][j - c[i]] + v[i],得出最优⽅案。
分支界限方法是一种用于解决优化问题的算法。
在动态规划算法中,分支界限方法被广泛应用于解决01背包问题。
01背包问题是一个经典的动态规划问题,其解题步骤如下:1. 确定问题:首先需要明确01背包问题的具体描述,即给定一组物品和一个背包,每个物品有自己的价值和重量,要求在不超过背包容量的情况下,选取尽可能多的物品放入背包,使得背包中物品的总价值最大。
2. 列出状态转移方程:对于01背包问题,可以通过列出状态转移方程来描述问题的求解过程。
假设dp[i][j]表示在前i个物品中,背包容量为j时能够获得的最大价值,则状态转移方程可以表示为:dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])3. 初始化边界条件:在动态规划中,需要对状态转移方程进行初始化,一般情况下,dp数组的第一行和第一列需要单独处理。
对于01背包问题,可以初始化dp数组的第一行和第一列为0。
4. 利用分支界限方法优化:针对01背包问题,可以使用分支界限方法来优化动态规划算法的效率。
分支界限方法采用广度优先搜索的思想,在每一步选择最有希望的分支,从而减少搜索空间,提高算法的效率。
5. 实际解题步骤:根据上述步骤,实际解决01背包问题的步骤可以概括为:确定问题,列出状态转移方程,初始化边界条件,利用分支界限方法优化,最终得到问题的最优解。
分支界限方法在解决01背包问题时起到了重要的作用,通过合理的剪枝策略,可以有效地减少动态规划算法的时间复杂度,提高问题的求解效率。
分支界限方法也可以应用于其他优化问题的求解过程中,在算法设计和实现中具有重要的理论和实际意义。
在实际应用中,分支界限方法需要根据具体问题进行灵活选择和调整,结合动态规划和剪枝策略,以便更好地解决各类优化问题。
掌握分支界限方法对于解决复杂问题具有重要的意义,也是算法设计和优化的关键技术之一。
分支界限方法在解决01背包问题的过程中,具有重要的作用。
算法设计与分析实验报告0_1背包一.问题描述假设有n件物品,每件物品有各自的重量W1,W2,……,Wn和与之对应的价值V1,V2,……,Vn。
设背包的容量为c,在不超过背包容量的前提下,求出获得最大价值总和的方案。
(0-1背包的情况下物品不可分割,只能选择放入,或者不放入背包中)。
二.求解思路1.贪心策略问题开始阶段,将所有物品按价值从高到低排列,每一次往背包里放入不超过背包容量的价值最大的物品,直到没有物品可放入为止。
但事实证明,由于物品的不可分割性,0-1背包并不适合贪心策略。
例:假设背包的容量为50,共有三件物品(重量,价值):(10,60),(20,100),(30,120)。
若使用贪心策略,则会选择一个(30,120)和一个(20,100)。
得到的价值总和是220。
而稍加计算便可知选取两个(20,100)和一个(10,60)可以得到更大的价值总和260。
因此贪心策略不能给出0-1背包的最优解。
后话:即使是普通背包问题(物品可分割),每次选择价值最大的物品也不能得到最优解。
正确的贪心策略应是:每次选择单位重量下价值最大的物品。
由于本次实验主要讨论的是0-1背包问题,这里就不给出该贪心策略的证明。
2.动态规划(1)证明0-1背包问题具有最优子结构性质:假设(x1,x2,……,xn)是容量为c的背包的一组最优解,其中xi的取值为0或1,表示是否放入背包中。
则必有(x2,x3,……,xn)为如下子问题的一组最优解:sum{xi*wi} (2<=i<=n)<=c-x1*w1利用反证法证明,假设(y1,y2,……,yn)是该子问题的一组最优解而(x2,x3,……,xn)不是。
则sum{yi*vi} > sum{xi*vi} (2<=i<=n)那么就可得到:x1*v1+ sum{yi*vi} > x1*v1+ sum{xi*vi} (2<=i<=n)则(x1,y2,……,yn)是原问题的最优解,而(x1,x2,……,xn)不是,与假设矛盾。
01背包问题,是用来介绍动态规划算法最经典的例子,网上关于01背包问题的讲解也很多,我写这篇文章力争做到用最简单的方式,最少的公式把01背包问题讲解透彻。
01背包的状态转换方程f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }只要你能通过找规律手工填写出上面这张表就算理解了01背包的动态规划算法。
首先要明确这张表是至底向上,从左到右生成的。
为了叙述方便,用e2单元格表示e行2列的单元格,这个单元格的意义是用来表示只有物品e时,有个承重为2的背包,那么这个背包的最大价值是0,因为e物品的重量是4,背包装不了。
对于d2单元格,表示只有物品e,d时,承重为2的背包,所能装入的最大价值,仍然是0,因为物品e,d都不是这个背包能装的。
同理,c2=0,b2=3,a2=6。
对于承重为8的背包,a8=15,是怎么得出的呢?根据01背包的状态转换方程,需要考察两个值,一个是f[i-1,j],对于这个例子来说就是b8的值9,另一个是f[i-1,j-Wi]+Pi;在这里,f[i-1,j]表示我有一个承重为8的背包,当只有物品b,c,d,e四件可选时,这个背包能装入的最大价值f[i-1,j-Wi]表示我有一个承重为6的背包(等于当前背包承重减去物品a的重量),当只有物品b,c,d,e四件可选时,这个背包能装入的最大价值f[i-1,j-Wi]就是指单元格b6,值为9,Pi指的是a物品的价值,即6由于f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于f[i-1,j] = 9,所以物品a应该放入承重为8的背包以下是actionscript3 的代码public function get01PackageAnswer(bagItems:Array,bagSize:int):Array{var bagMatrix:Array=[];var i:int;var item:PackageItem;for(i=0;i<bagItems.length;i++){bagMatrix[i] = [0];}for(i=1;i<=bagSize;i++){for(varj:int=0;j<bagItems.length;j++){item = bagItems[j] as PackageItem;if(item.weight > i){//i背包转不下itemif(j==0){bagMatrix[j][i] = 0;}else{bagMatrix[j][i]=bagMatrix[j-1][i];}}else{//将item装入背包后的价值总和var itemInBag:int;if(j==0){bagMatrix[j][i] = item.value;continue;}else{itemInBag = bagMatrix[j-1][i-item.weight]+item.value;}bagMatrix[j][i] = (bagMatrix[j-1][i] > itemInBag ? bagMatrix[j-1][i] : itemInBag)}}}//find answervar answers:Array=[];var curSize:int = bagSize;for(i=bagItems.length-1;i>=0;i--){item = bagItems[i] as PackageItem;if(curSize==0){break;}if(i==0 && curSize > 0){answers.push();break;}if(bagMatrix[i][curSize]-bagMatrix[i-1][curSize-item.weight ]==item.value){answers.push();curSize -= item.weight;}}return answers;}PackageItem类public class PackageItem{public var name:String;public var weight:int;public var value:int;public function PackageItem(name:String,weight:int,value:int){ = name;this.weight = weight;this.value = value;}}测试代码varnameArr:Array=['a','b','c','d','e'];var weightArr:Array=[2,2,6,5,4];var valueArr:Array=[6,3,5,4,6];var bagItems:Array=[];for(vari:int=0;i<nameArr.length;i++){var bagItem:PackageItem = new PackageItem(nameArr[i],weightArr[i],valueArr[i]);bagItems[i]=bagItem;}var arr:Array = ac.get01PackageAnswer(bagItems,10);。
0-1背包问题的枚举算法一、问题概述0-1背包问题是一种经典的优化问题,给定一组物品,每种物品都有自己的重量和价值,而你有一个限制容量的背包。
目标是在不超过背包容量的情况下,选择物品使得总价值最大化。
然而,在某些情况下,所有的物品都不能被放入背包中,这时就需要用到0-1背包问题的枚举算法。
二、算法原理枚举算法的基本思想是从所有可能的物品组合中逐个尝试,找出满足条件的组合。
对于0-1背包问题,我们可以枚举所有可能的物品组合,对于每个组合,计算其总价值和当前背包的剩余容量,如果总价值大于当前背包容量所能获得的最大价值,那么就将这个物品放入背包中,并更新背包剩余容量和总价值。
如果当前物品的价值小于或等于当前背包容量所能获得的最大价值,那么就将这个物品标记为0(表示已经考虑过),并继续尝试下一个物品。
最终得到的组合就是最优解。
三、算法实现以下是一个简单的Python实现:```pythondefknapsack_enumeration(items,capacity):#初始化结果列表和当前价值result=[]current_value=0#枚举所有可能的物品组合foriinrange(len(items)):#标记当前物品为0(已考虑过)items[i][1]=0#计算当前物品的价值并更新总价值forjinrange(len(items)):ifj<i:#不考虑之前的物品对当前物品的价值影响current_value+=items[j][1]*items[i][0]/capacityelse:#考虑之前的物品对当前物品的价值影响(假设不考虑前一个物品的重量)current_value+=items[j][0]*(capacity-items[i][0])/capacity#将当前物品从物品列表中移除(放入背包中)delitems[i]#将当前价值添加到结果列表中result.append(current_value)returnresult```四、应用场景枚举算法在许多实际应用中都有应用,如计算机科学、运筹学、工程学等。
c语言算法--贪婪算法---0/1背包问题在0 / 1背包问题中,需对容量为c 的背包进行装载。
从n 个物品中选取装入背包的物品,每件物品i 的重量为wi ,价值为pi 。
对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高,即n ?i=1pi xi 取得最大值。
约束条件为n ?i =1wi xi≤c 和xi?[ 0 , 1 ] ( 1≤i≤n)。
在这个表达式中,需求出xt 的值。
xi = 1表示物品i 装入背包中,xi =0 表示物品i 不装入背包。
0 / 1背包问题是一个一般化的货箱装载问题,即每个货箱所获得的价值不同。
货箱装载问题转化为背包问题的形式为:船作为背包,货箱作为可装入背包的物品。
例1-8 在杂货店比赛中你获得了第一名,奖品是一车免费杂货。
店中有n 种不同的货物。
规则规定从每种货物中最多只能拿一件,车子的容量为c,物品i 需占用wi 的空间,价值为pi 。
你的目标是使车中装载的物品价值最大。
当然,所装货物不能超过车的容量,且同一种物品不得拿走多件。
这个问题可仿照0 / 1背包问题进行建模,其中车对应于背包,货物对应于物品。
0 / 1背包问题有好几种贪婪策略,每个贪婪策略都采用多步过程来完成背包的装入。
在每一步过程中利用贪婪准则选择一个物品装入背包。
一种贪婪准则为:从剩余的物品中,选出可以装入背包的价值最大的物品,利用这种规则,价值最大的物品首先被装入(假设有足够容量),然后是下一个价值最大的物品,如此继续下去。
这种策略不能保证得到最优解。
例如,考虑n=2, w=[100,10,10], p =[20,15,15], c = 1 0 5。
当利用价值贪婪准则时,获得的解为x= [ 1 , 0 , 0 ],这种方案的总价值为2 0。
而最优解为[ 0 , 1 , 1 ],其总价值为3 0。
另一种方案是重量贪婪准则是:从剩下的物品中选择可装入背包的重量最小的物品。
01背包问题(01knapsackproblem)0 / 1 背包问题(0 / 1 knapsack problem)背包问题(Knapsack problem)是⼀种组合优化的问题。
问题可以描述为:给定⼀组物品,每种物品都有⾃⼰的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最⾼。
问题的名称来源于如何选择最合适的物品放置于给定背包中。
相似问题经常出现在商业、[组合数学],[计算复杂性理论]、[密码学]和[应⽤数学]等领域中。
也可以将背包问题描述为,即在总重量不超过W的前提下,总价值是否能达到V。
1、题⽬描述假设商店中有如下3个商品,他们的重量和价格如下:索引重量价值011500143000232000假如你是⼀个⼩偷,你有⼀个重量为4的包,每个商品只能偷⼀次,请问你怎么偷才会使得最后的价值最⼤?2、分析这种问题⼀般可以⽤动态规划很好地解决。
但是如果我不⽤动态规划,⽽是⽤搜索所有情况来解决也可以,每个商品都有偷或不偷的选项,所以n个商品就有n^2种情况,所以⽤遍历的⽅法时间复杂度为O(n^2) n为商品的数量现在我们假设B(k, w)表⽰的是前k个商品,在背包容量为w的情况下能偷的最⾼价值当现在⾯对的第k个物品重量太重时:B(k, w) = B(k-1, w),代表我在多了⼀个物品的选择的情况下,仍然和没有这件物品时的选择⼀样,所以结果也⼀样(因为我偷不了或者我不偷的情况)当第k个物品的重量我可以接受时:B(k, w) = B(k-1, w - 这件物品的重量) + 这件物品的价值代表我如果偷了这件物品,那剩下的w - 这件物品重量的空间可以容纳的最⼤价值就是在上⼀次选择时B(k-1, w - 这件物品的重量)的值。
再加上这件物品的价值就是我偷了这件物品的最⼤值。
所以,在衡量⼀个B(k, w)时,⾸先看⼀下能不能偷,能得话看⼀下偷还是不偷两个的最⼤值,就是B(k, w)的值,所以我们回到上⾯的问题,问题的解就是B(2,4)的值我们⽤⼆维数组 dp[][]来表⽰整个的过程可选商品 \ 背包容量012340号商品(1,1500)015001500150015000 ~ 1号商品(4,3000)015001500150030000 ~ 2号商品(3,2000)01500150020003500如图中加粗数字1500代表的是在有前两个商品,背包容量为2时可以偷的最⼤价值为1500图中加粗数字3000,即在有前2个商品,背包重量为4时,可以偷的最⼤价值为3000,这个数是这样算的:第⼆个商品(1号)重量为4,正好满⾜,如果偷的话所以价值为3000 + 0 = 3000如果不偷的话价值和只有1个商品,背包容量为4的价值⼀样,1500取最⼤值为3000所以问题的关键就在构建这个⼆维数组3、实现/*** 时间复杂度:O(n * capacity) n为商品数量,capacity为包的⼤⼩* 空间复杂度:O(n * capacity) 可以优化为capacity*/public class Main{/*** 0/1 背包问题* @param w w[i]代表i号物品的重量(从0开始)* @param v v[i]代表i号物品的价值(从0开始)* @param capacity 代表包的最⼤容量* @return 可以偷的商品的最⼤值*/public static int knapsack(int[] w, int[] v, int capacity){int goods = w.length; // 商品数int[][] dp = new int[goods][capacity + 1];// 初始化第⼀⾏,因为第⼀⾏上层没有元素了,即只有第⼀个商品时for(int j = 1; j <= capacity; j++){if(j >= w[0]) dp[0][j] = v[0];}// 前i个商品, 背包容量为j时偷得最⼤价值for(int i = 1; i < goods; i++) {for(int j = 1; j < capacity + 1; j++) {// 如果容量不够放下第i个商品if(w[i] > j) {dp[i][j] = dp[i-1][j];} else { // 如果可以放下这件商品dp[i][j] =Math.max(dp[i-1][j], v[i] + dp[i-1][j-w[i]]);}}}// System.out.println(Arrays.deepToString(dp));return dp[goods - 1][capacity];}}⽤滚动数组优化空间复杂度:因为如果我们从后往前构建每⼀⾏,那上⼀⾏保留的就可以在构建时候⽤/*** 时间复杂度:O(n * capacity) n为商品数量,capacity为包的⼤⼩* 空间复杂度:O(capacity)*/public class Main{/*** 0/1 背包问题* @param w w[i]代表i号物品的重量(从0开始)* @param v v[i]代表i号物品的价值(从0开始)* @param capacity 代表包的最⼤容量* @return 可以偷的商品的最⼤值*/public static int knapsack(int[] w, int[] v, int capacity){int goods = w.length; // 商品数int[] dp = new int[capacity + 1];// 前i个商品, 背包容量为j时偷得最⼤价值for(int i = 0; i < goods; i++) {for(int j = capacity; j > 0; j--) {// 如果能装下就更新,装不下就不更新(上⼀⾏的值)if(j - w[i] >= 0) {dp[j] = Math.max(dp[j], v[i] + dp[j - w[i]]);}}}return dp[capacity];}}。
一、问题描绘0/1 背包问题 :现有 n 种物件,对1<=i<=n,已知第i 种物件的重量为正整数W i,价值为正整数V i,背包能蒙受的最大载重量为正整数W ,现要求找出这n 种物件的一个子集,使得子集中物品的总重量不超出W 且总价值尽量大。
(注意:这里对每种物件或许全取或许一点都不取,不一样意只取一部分)二、算法剖析依据问题描绘,能够将其转变为以下的拘束条件和目标函数:nw i x i W(1)i1x i{ 0,1}( 1i n)nmax v i x i (2)i1于是,问题就归纳为找寻一个知足拘束条件( 1 ),并使目标函数式( 2 )达到最大的解向量 X(x1, x2 , x3 ,......, x n ) 。
第一说明一下0-1 背包问题拥有最优解。
假定 (x1, x2 , x3 ,......, x n ) 是所给的问题的一个最优解,则 (x2 , x3,......, x n ) 是下边问题的nw i x i W w1x1 maxn一个最优解:i 2v i x i。
假如不是的话,设( y2, y3 ,......, y n ) 是这x i{ 0,1}( 2i n)i 2n n n个问题的一个最优解,则v i y i v i x i,且 w1x1w i y i W 。
因此,i 2i 2i 2n n nv1x1v i y i v1 x1v i x i v i x i,这说明 (x1, y2 , y3 ,........, y n ) 是所给的0-1 背包问i 2i 2i 1题比 ( x1 , x2 , x3 ,........, x n ) 更优的解,进而与假定矛盾。
穷举法:用穷举法解决0-1 背包问题,需要考虑给定n 个物件会合的所有子集,找出所有可能的子集(总重量不超出背包重量的子集),计算每个子集的总重量,而后在他们中找到价值最大的子集。
因为程序过于简单,在这里就不再给出,用实例说明求解过程。