背包问题_背包问题java - CSDN
背包问题 订阅
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V?它是在1978年由Merkle和Hellman提出的。背包问题已经研究了一个多世纪,早期的作品可追溯到1897年 [1]  数学家托比亚斯·丹齐格(Tobias Dantzig,1884-1956)的早期作品 [2]  ,并指的是包装你最有价值或有用的物品而不会超载你的行李的常见问题。 展开全文
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V?它是在1978年由Merkle和Hellman提出的。背包问题已经研究了一个多世纪,早期的作品可追溯到1897年 [1]  数学家托比亚斯·丹齐格(Tobias Dantzig,1884-1956)的早期作品 [2]  ,并指的是包装你最有价值或有用的物品而不会超载你的行李的常见问题。
信息
外文名
Knapsack Problem
提出者
Merkle-Hellman
中文名
背包问题
应用领域
运筹学,应用数学,密码学等
背包问题应用
1998年的石溪布鲁克大学算法库的研究表明,在75个算法问题中,背包问题是第18个最受欢迎,第4个最需要解决的问题(前三为后kd树,后缀树和bin包装问题)。 [3]  背包问题出现在各种领域的现实世界的决策过程中,例如寻找最少浪费的方式来削减原材料, [4]  选择投资和投资组合, [5]  选择资产支持资产证券化 [6]  ,和生成密钥为Merkle-Hellman [7]  和其他背包密码系统。背包算法的一个早期应用是在测试的构建和评分中,测试者可以选择他们回答哪些问题。对于小例子来说,这是一个相当简单的过程,为测试者提供这样的选择。例如,如果考试包含12个问题,每个问题的价值为10分,测试者只需回答10个问题即可获得100分的最高分。然而,在点值的异质分布的测试 - 即不同的问题值得不同的点值 - 更难以提供选择。 Feuerman和Weiss提出了一个系统,其中学生被给予一个异质测试,共有125个可能的点。学生被要求尽可能回答所有的问题。在总点数加起来为100的问题的可能子集中,背包算法将确定哪个子集给每个学生最高的可能得分。 [8] 
收起全文
精华内容
参与话题
  • 动态规划之01背包问题(最易理解的讲解)

    万次阅读 多人点赞 2017-12-18 10:32:29
    01背包问题,是用来介绍动态规划算法最经典的例子,网上关于01背包问题的讲解也很多,我写这篇文章力争做到用最简单的方式,最少的公式把01背包问题讲解透彻。 01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi...

    01背包问题,是用来介绍动态规划算法最经典的例子,网上关于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件物品应该放入背包中吗 ?

    题目描述:

    假设山洞里共有a,b,c,d ,e这5件宝物(不是5种宝物),它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为10的背包, 怎么装背包,可以才能带走最多的财富。

    有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为10的背包,如何让背包里装入的物品具有最大的价值总和?

    name weight value 1 2 3 4 5 6 7 8 9 10
    a 2 6 0 6 6 9 9 12 12 15 15 15
    b 2 3 0 3 3 6 6 9 9 9 10 11
    c 6 5 0 0 0 6 6 6 6 6 10 11
    d 5 4 0 0 0 6 6 6 6 6 10 10
    e 4 6 0 0 0 6 6 6 6 6 6 6

    只要你能通过找规律手工填写出上面这张表就算理解了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(var j:int=0;j<bagItems.length;j++)
    				{
    					item = bagItems[j] as PackageItem;
    					if(item.weight > i)
    					{
    						//i背包转不下item
    						if(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 answer
    			var 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(item.name);
    					break;
    				}
    				if(bagMatrix[i][curSize]-bagMatrix[i-1][curSize-item.weight]==item.value)
    				{
    					answers.push(item.name);
    					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)
    		{
    			this.name = name;
    			this.weight = weight;
    			this.value = value;
    		}
    	}

    测试代码

    				var nameArr: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(var i: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);


    展开全文
  • 问题描述 有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和? 为方便讲解和理解,下面讲述的例子均先用具体的数字代入,即:eg:number=4,capacity=8 i...

    问题描述

    有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?

    为方便讲解和理解,下面讲述的例子均先用具体的数字代入,即:eg:number=4,capacity=8

    i(物品编号) 1 2 3 4
    w(体积) 2 3 4 5
    v(价值) 3 4 5 6

     

    总体思路

    根据动态规划解题步骤(问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成)找出01背包问题的最优解以及解组成,然后编写代码实现。

    动态规划的原理

    动态规划与分治法类似,都是把大问题拆分成小问题,通过寻找大问题与小问题的递推关系,解决一个个小问题,最终达到解决原问题的效果。但不同的是,分治法在子问题和子子问题等上被重复计算了很多次,而动态规划则具有记忆性,通过填写表把所有已经解决的子问题答案纪录下来,在新问题里需要用到的子问题可以直接提取,避免了重复计算,从而节约了时间,所以在问题满足最优性原理之后,用动态规划解决问题的核心就在于填表,表填写完毕,最优解也就找到。

    最优性原理是动态规划的基础,最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质:不论初始状态和初始决策如何,对于前面决策所造成的某一状态而言,其后各阶段的决策序列必须构成最优策略”。

    背包问题的解决过程

    在解决问题之前,为描述方便,首先定义一些变量:Vi表示第 i 个物品的价值,Wi表示第 i 个物品的体积,定义V(i,j):当前背包容量 j,前 i 个物品最佳组合对应的价值,同时背包问题抽象化(X1,X2,…,Xn,其中 Xi 取0或1,表示第 i 个物品选或不选)。

    1、建立模型,即求max(V1X1+V2X2+…+VnXn);

    2、寻找约束条件,W1X1+W2X2+…+WnXn<capacity;

    3、寻找递推关系式,面对当前商品有两种可能性:

    • 包的容量比该商品体积小,装不下,此时的价值与前i-1个的价值是一样的,即V(i,j)=V(i-1,j);
    • 还有足够的容量可以装该商品,但装了也不一定达到当前最优价值,所以在装与不装之间选择最优的一个,即V(i,j)=max{V(i-1,j),V(i-1,j-w(i))+v(i)}。

    其中V(i-1,j)表示不装,V(i-1,j-w(i))+v(i) 表示装了第i个商品,背包容量减少w(i),但价值增加了v(i);

    由此可以得出递推关系式:

    • j<w(i)      V(i,j)=V(i-1,j)
    • j>=w(i)     V(i,j)=max{V(i-1,j),V(i-1,j-w(i))+v(i)}

    这里需要解释一下,为什么能装的情况下,需要这样求解(这才是本问题的关键所在!):

    可以这么理解,如果要到达V(i,j)这一个状态有几种方式?

    肯定是两种,第一种是第i件商品没有装进去,第二种是第i件商品装进去了。没有装进去很好理解,就是V(i-1,j);装进去了怎么理解呢?如果装进去第i件商品,那么装入之前是什么状态,肯定是V(i-1,j-w(i))。由于最优性原理(上文讲到),V(i-1,j-w(i))就是前面决策造成的一种状态,后面的决策就要构成最优策略。两种情况进行比较,得出最优。

    4、填表,首先初始化边界条件,V(0,j)=V(i,0)=0;

    然后一行一行的填表:

    • 如,i=1,j=1,w(1)=2,v(1)=3,有j<w(1),故V(1,1)=V(1-1,1)=0;
    • 又如i=1,j=2,w(1)=2,v(1)=3,有j=w(1),故V(1,2)=max{ V(1-1,2),V(1-1,2-w(1))+v(1) }=max{0,0+3}=3;
    • 如此下去,填到最后一个,i=4,j=8,w(4)=5,v(4)=6,有j>w(4),故V(4,8)=max{ V(4-1,8),V(4-1,8-w(4))+v(4) }=max{9,4+6}=10……

    所以填完表如下图:

    5、表格填完,最优解即是V(number,capacity)=V(4,8)=10。

     

    代码实现

    为了和之前的动态规划图可以进行对比,尽管只有4个商品,但是我们创建的数组元素由5个。

    #include<iostream>
    using namespace std;
    #include <algorithm>
    
    int main()
    {
    	int w[5] = { 0 , 2 , 3 , 4 , 5 };			//商品的体积2、3、4、5
    	int v[5] = { 0 , 3 , 4 , 5 , 6 };			//商品的价值3、4、5、6
    	int bagV = 8;					        //背包大小
    	int dp[5][9] = { { 0 } };			        //动态规划表
    
    	for (int i = 1; i <= 4; i++) {
    		for (int j = 1; j <= bagV; j++) {
    			if (j < w[i])
    				dp[i][j] = dp[i - 1][j];
    			else
    				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
    		}
    	}
    
    	//动态规划表的输出
    	for (int i = 0; i < 5; i++) {
    		for (int j = 0; j < 9; j++) {
    			cout << dp[i][j] << ' ';
    		}
    		cout << endl;
    	}
    
    	return 0;
    }

     

    背包问题最优解回溯

    通过上面的方法可以求出背包问题的最优解,但还不知道这个最优解由哪些商品组成,故要根据最优解回溯找出解的组成,根据填表的原理可以有如下的寻解方式:

    • V(i,j)=V(i-1,j)时,说明没有选择第i 个商品,则回到V(i-1,j);
    • V(i,j)=V(i-1,j-w(i))+v(i)时,说明装了第i个商品,该商品是最优解组成的一部分,随后我们得回到装该商品之前,即回到V(i-1,j-w(i));
    • 一直遍历到i=0结束为止,所有解的组成都会找到。

    就拿上面的例子来说吧:

    • 最优解为V(4,8)=10,而V(4,8)!=V(3,8)却有V(4,8)=V(3,8-w(4))+v(4)=V(3,3)+6=4+6=10,所以第4件商品被选中,并且回到V(3,8-w(4))=V(3,3);
    • 有V(3,3)=V(2,3)=4,所以第3件商品没被选择,回到V(2,3);
    • 而V(2,3)!=V(1,3)却有V(2,3)=V(1,3-w(2))+v(2)=V(1,0)+4=0+4=4,所以第2件商品被选中,并且回到V(1,3-w(2))=V(1,0);
    • 有V(1,0)=V(0,0)=0,所以第1件商品没被选择。

     

    代码实现

    背包问题最终版详细代码实现如下:

    #include<iostream>
    using namespace std;
    #include <algorithm>
    
    int w[5] = { 0 , 2 , 3 , 4 , 5 };			//商品的体积2、3、4、5
    int v[5] = { 0 , 3 , 4 , 5 , 6 };			//商品的价值3、4、5、6
    int bagV = 8;					        //背包大小
    int dp[5][9] = { { 0 } };			        //动态规划表
    int item[5];					        //最优解情况
    
    void findMax() {					//动态规划
    	for (int i = 1; i <= 4; i++) {
    		for (int j = 1; j <= bagV; j++) {
    			if (j < w[i])
    				dp[i][j] = dp[i - 1][j];
    			else
    				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
    		}
    	}
    }
    
    void findWhat(int i, int j) {				//最优解情况
    	if (i >= 0) {
    		if (dp[i][j] == dp[i - 1][j]) {
    			item[i] = 0;
    			findWhat(i - 1, j);
    		}
    		else if (j - w[i] >= 0 && dp[i][j] == dp[i - 1][j - w[i]] + v[i]) {
    			item[i] = 1;
    			findWhat(i - 1, j - w[i]);
    		}
    	}
    }
    
    void print() {
    	for (int i = 0; i < 5; i++) {			//动态规划表输出
    		for (int j = 0; j < 9; j++) {
    			cout << dp[i][j] << ' ';
    		}
    		cout << endl;
    	}
    	cout << endl;
    
    	for (int i = 0; i < 5; i++)			//最优解输出
    		cout << item[i] << ' ';
    	cout << endl;
    }
    
    int main()
    {
    	findMax();
    	findWhat(4, 8);
    	print();
    
    	return 0;
    }

     

    展开全文
  • 问题描述:给定n个物体(它们的重量为:w1,w2,......,wn,价值为:v1,v2,......,vn) 和 一个承受重量为W的背包,问怎么选取这些物体,放在背包中(不超过背包的承重),让所取的子集达到最大价值。...

    一、01背包

    问题描述:给定n个物体(它们的重量为:w1,w2,......,wn,价值为:v1,v2,......,vn) 和 一个承受重量为W的背包,问怎么选取这些物体,放在背包中(不超过背包的承重),让所取的子集达到最大价值。

    1、基本实现

    首先,我们很自然想到穷举法,只要给出n个物体的所有组合(子集),分别各个子集的总价值,去掉那些总重量超过背包承重W的子集之后,对剩下的子集中找到总价值最大的那一个,就是我们想要的结果了。

    但是,由于n各物体的有2^n个子集,所以上面的做法的时间复杂度将是O(2^n),除非n很小,否则时间性能消耗非常严重。

    我们换一种思路,如果物体有n-1个,在背包容量为0,1,2,......,W各个情况下所能得到的最大价值都已经知道,那么当我们多考虑一个物体,即物体有n个时,就可以分为两个情况进行考虑:(1)第n个物体不放进背包中;(2)第n个物体放进背包。

    对于第一种情况,考虑n个物体,跟考虑n-1个物体没有区别,所以考虑n个物体的情况下,在一定承重量的背包中所能得到的最大价值等于只考虑n-1个物体在同等承重量的背包下所能得到的最大价值。

    对于第二种情况,则最大价值 = 物体n的价值vn + 背包在剩余空间(W-wn)下只考虑n-1个物体所能达到的最大价值。

    如下面递推式所示,

    其中,F(i,j)表示前 i 个物体(1≤ i ≤n)在背包承重为 j 时,所能达到的最大价值。如果把它看成一个状态的话,那么也就是说,状态F(i,j)的值等于状态F(i-1,j)、状态F(i-1,j-wi)与vi之和 两者中的最大值。那么要求 i 个物体在一定承重背包中可取的最大价值,只需考虑 i-1 个物体在不同承重量(0,1, 2, ......,W)的背包下可取的最大价值。类似地,要想知道 i-1 个物体在一定承重的背包中可取的最大价值,只需知道 i-2 个物体在不同承重量的背包中可取的最大价值。以此类推,直到所考虑的物体个数变为 1 。

    所以,只要我们知道物体个数为 1 时,在不同承重量的背包中所能取到的最大价值,就可以依次求物体个数为2,3,......,n的情况下在不同承重量的背包中所能取的最大价值。

    初始条件为:i = 1     当 j ≥ w1时,F(1,j) = v1; 当 0≤ j <w1时,F(1,j) = 0.

     知道了上面的递推式、初始条件,就可以写出01背包的代码了。

    // 二维实现
    
     public class PkgTest {
    	public static void main(String[] args) {
    		//w[]:物品重量,v[]:物品价值,m:背包承重,n:物品个数,maxValue[][]:状态
    		int[] w = {0, 10, 3, 4, 5}; //第一个数为0,是为了让输出时,i表示有i个物品
    		int[] v = {0, 3, 4, 6, 7};
    		int m = 10;
    		int n = 4;
    		int[][] maxValue = new int[5][16];
    		
    		// 01背包算法
    		for (int i=1; i<=n; i++) { //第一个物体 是 第1行
    			for (int j=0; j<=m; j++) {
    				if (i > 0) {
    					maxValue[i][j] = maxValue[i-1][j];
    					if (j >= w[i]) {
    						maxValue[i][j] = max(maxValue[i][j], maxValue[i-1][j-w[i]] + v[i]);
    						//注:maxValue[i][j]其实就是maxValue[i-1][j]   因为上面的赋值
    					}
    				} else {          //初始化,只考虑一个物体
    					if (j >= w[1]) {
    						maxValue[1][j] = v[1];
    					}
    				}
    			}
    		}
    		
    		System.out.println("4个物品在背包承重为10的情况下的组合的最大价值为:"+maxValue[n][m]);
    		System.out.println();
    		
    		// 打印背包的不同承重量
    		System.out.print("   " + "\t");
    		for (int i=0; i<=m; i++) {
    			System.out.print(i + "\t");
    		}
    		System.out.println();
    		
    		// 打印01背包算法 得到的状态矩阵值
    		for (int i=1; i<=n; i++) {
    			System.out.print("i="+ i +"\t");
    			for (int j=0; j<=m; j++) {
    				System.out.print(maxValue[i][j]+"\t");
    			}
    			System.out.println();
    		}
    	}
    	
    	public static int max(int a, int b) {
    		if (a > b) {
    			return a;
    		}
    		return b;
    	}
     }

    结果如下图所示,

    2、滚动数组实现

    上面的基本实现时间复杂度为O(nW),空间复杂度为O(nW),事实上空间可以做优化。我们可以看到,第 i 层的状态至于第 i-1 层的状态有关,与第 i-2 层的状态没有直接关系,如下面的图所示,除了第一层的初始条件,其他每一层的状态值的求解依赖于上一层。

    所以,我们可以用只有两行的二维数组 maxValue[2][ ] 来存储,如下面代码所示。

    // 滚动数组实现
    
    public class PkgTest {
    	public static void main(String[] args) {
    		int[] w = {0,10, 3, 4, 5};
    		int[] v = {0,3, 4, 6, 7};
    		int m = 10;
    		int n = 4;
    		int k = 0;  // k的作用是指向数组的某一行(两行其中之一),不能再用下标i来指定数组的行数了
    		int[][] maxValue = new int[2][16];
    		
    		for (int i=1; i<=n; i++) { 
    			for (int j=0; j<=m; j++) {
    				if (i > 1) {
    					k = i & 1; // k = i % 2  获得滚动数组当前索引 k
    					maxValue[k][j] = maxValue[k^1][j]; // k ^ 1  获得滚动数组逻辑上的“上一行”
    					if (j >= w[i]) {
    						maxValue[k][j] = max(maxValue[k][j], maxValue[k^1][j-w[i]] + v[i]);
    					}
    				} else {  
    					if (j >= w[1]) {
    						maxValue[1][j] = v[0];
    					}
    				}
    			}
    		}
    		
    		System.out.println("4个物品在背包承重为10的情况下的组合的最大价值为:"+maxValue[k][m]);
    		System.out.println();
    		
    		System.out.print("i=0"+"\t");
    		for (int i=0; i<=m; i++) {
    			System.out.print(maxValue[1][i] + "\t");
    		}
    		System.out.print("\ni=1"+"\t");
    		for (int i=0; i<=m; i++) {
    			System.out.print(maxValue[0][i] + "\t");
    		}
    	}
    	
    	public static int max(int a, int b) {
    		if (a > b) {
    			return a;
    		}
    		return b;
    	}
    }

    需要注意的是,代码中我们不再用下标 i 指向数组的索引,而是用 k 指向数组,k=0、k=1表示相邻的两行状态值,k=1不一定是k=0逻辑上的上一行,需要看具体情况(这个把整个过程画一下就知道了)。

    初始化时,我们在标号为1的一行输入状态值。

    当 i = 2 大于1时,

    由于       

    此时 k = 0指向数组的另一行,我们通过 k ^ 1找到 k 逻辑上的“上一行”,并通过“上一行”算出本行中的状态值

    以此类推,不断算出并刷新各行的状态值,直到最后两行。

    运行结果如下所示,

    3、一维数组实现

    01背包还可以用一维数组实现,只不过此时的递推式 & 初始条件就需要做些改变了。要想用一维数组存放所有状态,也就是让该数组某个时间是第 i-1 层的状态,而过一段时间之后则成为第 i 层的状态。如下面所演示的,初始状态下,一维数组 maxValue[ ]存放的是 i = 1 时的状态值(对应上面的F[ 1 ][ j ],j = 0,1,2,......,W)

    而当 i = 2 时,我们就需要计算 第二行的状态值,并把它们覆盖到maxValue[ ]一维数组之上。

    问题是怎么覆盖呢?如果我们还是跟二维数组一样从前往后遍历数组,覆盖的过程中某一时刻如下图所示,其中数组前面部分是属于 i=2 层的状态值,后面部分属于 i=1 层的状态值。

    但是,当我们继续计算并写入 i=2 的状态值时,很有可能用到 i=1 的某个状态值,而这个状态值却已经被覆盖掉了,比如,我们计算 i=2 的maxValue[ 6 ]时,要找到 i=1 的 maxValue[ 3 ] 状态值,本来它应该为0,但却变成4,如果我们用4去计算

    maxValue[ 6 ],就会得到错误的结果。

    事实上,我们覆盖的过程中,应该采用从后到前的顺序遍历。首先,改写maxValue[ W ]的值。

    改写之后,原来maxValue[ W ]的值就由3变为4。接着,改写maxValue[ W-1 ],由于计算 i=2 的maxValue[ W-1 ] 不需要用到 i=1 的maxValue[ W ]状态,所以,maxValue[ W ]的改动不影响maxValue[ W-1 ]的计算。

    以此类推,就可以在原来的数组上面不断覆盖最新一层的状态值了。

    上面的过程的递推式为:

    初始条件为:i = 1     当 v≥ w1时,F(v) = v1; 当 0≤ j<w1时,F(v) = 0.

    代码实现如下,

    // 一维数组
    
    public class PkgTest {
    	public static void main(String[] args) {
    		int[] w = {0,10, 3, 4, 5};
    		int[] v = {0,3, 4, 6, 7};
    		int m = 10;
    		int n = 4;
    		//int k = 0;
    		int[] maxValue = new int[16];
    		
    		for (int i=1; i<=n; i++) {
    			for (int j=m; j>=w[i]; j--) {
    				maxValue[j] = max(maxValue[j], maxValue[j-w[i]] + v[i]);
    			}
    			
    			//验证  结果和二维实现的输出结果完全一样 
    			//for (int k=0; k<=m; k++) {
    			//	System.out.print(maxValue[k] + "\t");
    			//}
    			//System.out.println();
    		}
    		
    		System.out.println("4个物品在背包承重为10的情况下的组合的最大价值为:"+maxValue[m]);
    		System.out.println();
    		
    		for (int i=0; i<=m; i++) {
    			System.out.print(maxValue[i] + "\t");
    		}
    	}
    	
    	public static int max(int a, int b) {
    		if (a > b) {
    			return a;
    		}
    		return b;
    	}
    }

    运行结果如下所示,

    4、小结

    尽管滚动数组、一维数组能省一些空间,但是,这两种做法比较适合只求最大价值的需求。当需要输出最佳方案时,我们常常要回溯历史信息,这时,一般就只能用二维数组这种保存有各个状态值的方法了。

    这里再稍微讲下滚动数组。事实上,我们可以在一些其它算法看到滚动数组的思想。比如,在斐波那契数列中,我们一般把各个斐波那契数存在一个数组中。但如果我们只需要打印一遍斐波那契数列,或者只需要计算某个斐波那契数时,我们可以只用三个变量(或者三个空间大小的数组),用前两个变量存放初始斐波那契数,然后两者相加之和放在第三个变量。不断地滚动下去,直到求得所需要的斐波那契数。

    再比如,二叉树删除一个结点。我们通常让两个引用(或指针)一个指向某个结点,一个指向该节点的父节点。两个引用不断往树深处滚动,直到指向子节点的引用找到待删除节点。这时,我们就可以利用指向父节点的引用对其进行删除了。

    二、完全背包

    问题描述:完全背包是在01背包的基础上加了个条件——这n种物品都有无限的数量可以取,问怎样拿才可以实现价值最大化。

    1、基本实现

    虽然题意中每种有无限件,但这里有个隐藏条件:背包承重量的固定性导致每种最多只能取某个值,再多就放不下了,这个值就是W / wi。也就是说,对于第 i 种物品,它可以取0,1,2,......,W / wi(向下取整)件。而在01背包中,对于第 i 种物品,只能取0,1件。我们可以看到,01背包其实就是完全背包的一个特例。所以我们可以用类似01背包的思路写出完全背包的基本算法。

    前面给出的01背包的状态转移方程也可以写成这种形式:

    下面是基本实现的代码,

    // 完全背包的基本实现
    
     public class CompleteTest {
    	public static void main(String[] args) {	
    		int[] w = {0,10, 3, 4, 5};
    		int[] v = {0,3, 4, 6, 7};
    		int m = 10;
    		int n = 4;
    		int[][] maxValue = new int[5][16];
    		
    		for (int i=1; i<=n; i++) { 
    			for (int j=0; j<=m; j++) {
    				if (i > 1) {
    					maxValue[i][j] = maxValue[i-1][j];
    					//if (j >= v[i]) {
    					//	maxValue[i][j] = max(maxValue[i][j], maxValue[i-1][j-v[i]] + w[i]);
    					//}
    					if (j/w[i] >= 1) {
    						int maxTmp = 0;   
    						// 对于i个物品,进行j/w[i]次比较得到最大值;而01背包中只需要进行1次比较
    						for (int k=1; k<=j/w[i]; k++) {    
    							if (maxValue[i-1][j-k*w[i]] + k*v[i] > maxTmp) {
    								maxTmp = maxValue[i-1][j-k*w[i]] + k*v[i];
    							}
    						}
    						maxValue[i][j] = max(maxValue[i][j], maxTmp);
    					}
    				} else {
    					//if (j >= v[0]) {
    					//	maxValue[0][j] = w[0];
    					//}
    					if (j/w[1] >= 1) {
    						maxValue[1][j] = j/w[1] * v[1];
    					}
    				}
    			}
    		}
    		
    		System.out.println("4个物品在背包承重为10的情况下的组合的最大价值为:"+maxValue[n][m]);
    		System.out.println();
    		
    		// 打印背包的不同承重量
    		System.out.print("   " + "\t");
    		for (int i=0; i<=m; i++) {
    			System.out.print(i + "\t");
    		}
    		System.out.println();
    		
    		// 打印01背包算法 得到的状态矩阵值
    		for (int i=1; i<=n; i++) {
    			System.out.print("i="+ i +"\t");
    			for (int j=0; j<=m; j++) {
    				System.out.print(maxValue[i][j]+"\t");
    			}
    			System.out.println();
    		}
    	}
    	
    	public static int max(int a, int b) {
    		if (a > b) {
    			return a;
    		}
    		return b;
    	}
     }

    代码跟01背包的二维数组实现几乎一模一样,我们只需在01背包基本实现的代码中注释掉两段代码,再略微修改就变成完全背包的了。

    运行结果如图所示,结果和01背包不同。

    2、时间优化

    基本实现中的时间复杂度为O(nW\sum W/wi) = O(nW*max(W / wi))

     

    3、空间优化

    基本实现采用的是二维数组,事实上我们也可以用一维数组实现。完全背包的一维数组实现和01背包也是几乎完全相同,唯一差别是完全背包的内循环是正向遍历,而01背包的内循环是逆向遍历。

    // 完全背包的一维数组实现
    
    public class CompleteTest2 {
    	public static void main(String[] args) {
    		int[] w = {0,10, 3, 4, 5};
    		int[] v = {0,3, 4, 6, 7};
    		int m = 10;
    		int n = 4;
    		int[] maxValue = new int[16];
    		
    		for (int i=1; i<=n; i++) {
    			//for (int j=m; j>=w[i]; j--) {
    			// 正序遍历; 01背包是逆序遍历
    			for (int j=w[i]; j<=m; j++) {
    				maxValue[j] = max(maxValue[j], maxValue[j-w[i]] + v[i]);
    			}
    			
    			//验证  结果和二维实现的输出结果完全一样 
    			//for (int k=0; k<=m; k++) {
    			//	System.out.print(maxValue[k] + "\t");
    			//}
    			//System.out.println();
    		}
    		
    		System.out.println("4个物品在背包承重为10的情况下的组合的最大价值为:"+maxValue[m]);
    		System.out.println();
    		
    		for (int i=0; i<=m; i++) {
    			System.out.print(maxValue[i] + "\t");
    		}
    	}
    	
    	public static int max(int a, int b) {
    		if (a > b) {
    			return a;
    		}
    		return b;
    	}
    }

    运行结果如下,

    三、多重背包

    问题描述:多重背包是在01背包的基础上,加了个条件:第 i 件物品有ni件。

    1、基本实现

    我们考虑一下,如果所有ni都满足ni ≥ W / wi,那不就变成完全背包的问题了么。可见,完全背包的基本实现思路也可以应用到多重背包的基本实现。对于多重背包的基本实现,与完全背包是基本一样的,不同就在于物品的个数上界不再是v/c[i]而是n[i]与v/c[i]中较小的那个。所以我们要在完全背包的基本实现之上,再考虑这个上界问题。

    代码实现如下所示,代码与完全背包的区别除了多了个表示物品个数的数组n[ ]之外,只在内循环的控制条件那里。

    // 多重背包的基本实现
    
     public class MultipleTest {
    	public static void main(String[] args) {	
    		int[] w = {0,10, 3, 4, 5};
    		int[] v = {0,3, 4, 6, 7};
    		//第i个物品对应的个数
    		int[] mount = {0,5,1,2,1};
    		int m = 10;
    		int n = 4;
    		int[][] maxValue = new int[5][16];
    		
    		for (int i=1; i<=n; i++) { 
    			for (int j=0; j<=m; j++) {
    				if (i > 1) {
    					maxValue[i][j] = maxValue[i-1][j];
    					if (j/w[i] >= 1) {
    						int maxTmp = 0;   
    						//for (int k=1; k<=j/w[i]; k++) {    
    						//多重背包与完全背包的区别只在内循环这里
    						for (int k=1; k<=j/w[i] && k<=mount[i]; k++) {
    							if (maxValue[i-1][j-k*w[i]] + k*v[i] > maxTmp) {
    								maxTmp = maxValue[i-1][j-k*w[i]] + k*v[i];
    							}
    						}
    						maxValue[i][j] = max(maxValue[i][j], maxTmp);
    					}
    				} else {
    					if (j/w[1] >= 1) {
    						maxValue[1][j] = j/w[1] * v[1];
    					}
    				}
    			}
    		}
    		
    		System.out.println("4个物品在背包承重为10的情况下的组合的最大价值为:"+maxValue[n][m]);
    		System.out.println();
    		
    		// 打印背包的不同承重量
    		System.out.print("   " + "\t");
    		for (int i=0; i<=m; i++) {
    			System.out.print(i + "\t");
    		}
    		System.out.println();
    		
    		// 打印01背包算法 得到的状态矩阵值
    		for (int i=1; i<=n; i++) {
    			System.out.print("i="+ i +"\t");
    			for (int j=0; j<=m; j++) {
    				System.out.print(maxValue[i][j]+"\t");
    			}
    			System.out.println();
    		}
    	}
    	
    	public static int max(int a, int b) {
    		if (a > b) {
    			return a;
    		}
    		return b;
    	}
     }

    运行结果如下所示,

    2、时间优化(通过二进制拆分转化为01背包问题)

    待续

    3、优先队列实现

    待续

    四、小结

    本质上,完全背包是多重背包的一个特例:当n[i]都大于等于 V / c[i]  时,多重背包就变为完全背包问题了;01背包是完全背包的一个特例:当第i种物品由可以取0,1,2,...件变为只能取0,1件时(也就是从V / c[i] + 1 种状态 变为 2种状态),完全背包就变为01背包问题了。三者两两之间的关系有点像集合之间的包含关系。

     

    展开全文
  • 彻底理解0-1背包问题

    万次阅读 多人点赞 2020-08-26 19:01:09
    0-1背包问题 给定n个重量为w1,w2,w3,…,wn,价值为v1,v2,v3,…,vn的物品和容量为C的背包,求这个物品中一个最有价值的子集,使得在满足背包的容量的前提下,包内的总价值最大 0-1背包问题指的是每个物品只能使用一...

    0-1背包问题

    给定n个重量为w1w_1w2w_2,w3w_3,…,wnw_n,价值为v1v_1,v2v_2,v3v_3,…,vnv_n的物品和容量为CC的背包,求这个物品中一个最有价值的子集,使得在满足背包的容量的前提下,包内的总价值最大

    0-1背包问题指的是每个物品只能使用一次

    递归方法

    首先我们用递归的方式来尝试解决这个问题
    我们用F(n,C)F(n,C)表示将前nn个物品放进容量为CC的背包里,得到的最大的价值。
    我们用自顶向下的角度来看,假如我们已经进行到了最后一步(即求解将nn个物品放到背包里获得的最大价值),此时我们便有两种选择

    1. 不放第nn个物品,此时总价值为F(n1,C)F(n-1,C)
    2. 放置第nn个物品,此时总价值为vn+F(n1,Cwn)v_n+F(n-1,C-w_n)

    两种选择中总价值最大的方案就是我们的最终方案,递推式(有时也称之为状态转移方程)如下
    F(i,C)=max(F(i1,C),v(i)+F(i1,Cw(i)))F(i,C)=max(F(i-1,C),v(i)+F(i-1,C-w(i)))
    编程实现如下:

    public class KnapSack01 {
        /**
         * 解决背包问题的递归函数
         *
         * @param w        物品的重量数组
         * @param v        物品的价值数组
         * @param index    当前待选择的物品索引
         * @param capacity 当前背包有效容量
         * @return 最大价值
         */
        private static int solveKS(int[] w, int[] v, int index, int capacity) {
            //基准条件:如果索引无效或者容量不足,直接返回当前价值0
            if (index < 0 || capacity <= 0)
                return 0;
    
            //不放第index个物品所得价值
            int res = solveKS(w, v, index - 1, capacity);
            //放第index个物品所得价值(前提是:第index个物品可以放得下)
            if (w[index] <= capacity) {
                res = Math.max(res, v[index] + solveKS(w, v, index - 1, capacity - w[index]));
            }
            return res;
        }
    
        public static int knapSack(int[] w, int[] v, int C) {
            int size = w.length;
            return solveKS(w, v, size - 1, C);
        }
    
        public static void main(String[] args){
            int[] w = {2,1,3,2};
            int[] v = {12,10,20,15};
            System.out.println(knapSack(w,v,5));
        }
    }
    
    

    记忆化搜索

    我们用递归方法可以很简单的实现以上代码,但是有个严重的问题就是,直接采用自顶向下的递归算法会导致要不止一次的解决公共子问题,因此效率是相当低下的。
    我们可以将已经求得的子问题的结果保存下来,这样对子问题只会求解一次,这便是记忆化搜索。
    下面在上述代码的基础上加上记忆化搜索

    public class KnapSack01 {
        private static int[][] memo;
    
        /**
         * 解决背包问题的递归函数
         *
         * @param w        物品的重量数组
         * @param v        物品的价值数组
         * @param index    当前待选择的物品索引
         * @param capacity 当前背包有效容量
         * @return 最大价值
         */
        private static int solveKS(int[] w, int[] v, int index, int capacity) {
            //基准条件:如果索引无效或者容量不足,直接返回当前价值0
            if (index < 0 || capacity <= 0)
                return 0;
    
            //如果此子问题已经求解过,则直接返回上次求解的结果
            if (memo[index][capacity] != 0) {
                return memo[index][capacity];
            }
    
            //不放第index个物品所得价值
            int res = solveKS(w, v, index - 1, capacity);
            //放第index个物品所得价值(前提是:第index个物品可以放得下)
            if (w[index] <= capacity) {
                res = Math.max(res, v[index] + solveKS(w, v, index - 1, capacity - w[index]));
            }
            //添加子问题的解,便于下次直接使用
            memo[index][capacity] = res;
            return res;
        }
    
        public static int knapSack(int[] w, int[] v, int C) {
            int size = w.length;
            memo = new int[size][C + 1];
            return solveKS(w, v, size - 1, C);
        }
    
        public static void main(String[] args) {
            int[] w = {2, 1, 3, 2};
            int[] v = {12, 10, 20, 15};
            System.out.println(knapSack(w, v, 5));
        }
    }
    
    

    动态规划算法

    在这里插入图片描述
    在这里插入图片描述

    public class KnapSack01 {
        public static int knapSack(int[] w, int[] v, int C) {
            int size = w.length;
            if (size == 0) {
                return 0;
            }
    
            int[][] dp = new int[size][C + 1];
            //初始化第一行
            //仅考虑容量为C的背包放第0个物品的情况
            for (int i = 0; i <= C; i++) {
                dp[0][i] = w[0] <= i ? v[0] : 0;
            }
    		//填充其他行和列
            for (int i = 1; i < size; i++) {
                for (int j = 0; j <= C; j++) {
                    dp[i][j] = dp[i - 1][j];
                    if (w[i] <= j) {
                        dp[i][j] = Math.max(dp[i][j], v[i] + dp[i - 1][j - w[i]]);
                    }
                }
            }
            return dp[size - 1][C];
        }
    
        public static void main(String[] args) {
            int[] w = {2, 1, 3, 2};
            int[] v = {12, 10, 20, 15};
            System.out.println(knapSack(w, v, 5));
        }
    }
    
    

    空间复杂度的极致优化

    上面的动态规划算法使用了O(n*C)的空间复杂度(因为我们使用了二维数组来记录子问题的解),其实我们完全可以只使用一维数组来存放结果,但同时我们需要注意的是,为了防止计算结果被覆盖,我们必须从后向前分别进行计算
    在这里插入图片描述
    我们仍然假设背包空间为5,根据F(i,C)=max(F(i1,C),v(i)+F(i1,Cw(i)))F(i,C)=max(F(i-1,C),v(i)+F(i-1,C-w(i)))我们可以知道,当我们利用一维数组进行记忆化的时候,我们只需要使用到当前位置的值和该位置之前的值,举个例子
    假设我们要计算F(i,4)F(i,4),我们需要用到的值为F(i1,4)F(i-1,4)F(i1,4w(i))F(i-1,4-w(i)),因此为了防止结果被覆盖,我们需要从后向前依次计算结果
    最终的动态规划代码如下

    public class KnapSack01 {
        public static int knapSack(int[] w, int[] v, int C) {
            int size = w.length;
            if (size == 0) {
                return 0;
            }
    
            int[] dp = new int[C + 1];
            //初始化第一行
            //仅考虑容量为C的背包放第0个物品的情况
            for (int i = 0; i <= C; i++) {
                dp[i] = w[0] <= i ? v[0] : 0;
            }
    
            for (int i = 1; i < size; i++) {
                for (int j = C; j >= w[i]; j--) {
                    dp[j] = Math.max(dp[j], v[i] + dp[j - w[i]]);
                }
            }
            return dp[C];
        }
    
        public static void main(String[] args) {
            int[] w = {2, 1, 3, 2};
            int[] v = {12, 10, 20, 15};
            System.out.println(knapSack(w, v, 5));
        }
    }
    
    

    利用背包问题的思想解决问题

    leetcode 416 Partition Equal Subset Sum

    给定一个仅包含正整数的非空数组,确定该数组是否可以分成两部分,要求两部分的和相等

    问题分析

    该问题我们可以利用背包问题的思想进行求解。

    假设给定元素个数为nn的数组arr,数组元素的和为sum,对应于背包问题,等价于有nn个物品,每个物品的重量和价值均为为arr[i],背包的限重为sum/2,求解背包中的物品最大价值为多少?

    class Solution {
        private boolean knapSack(int[] nums,int sum){
            int size = nums.length;
            
            boolean[] dp = new boolean[sum + 1];
            for (int i = 0;i <= sum;i ++){
               dp[i] = i == nums[0];
            }
            
            for (int i = 1;i < size;i++){
                for (int j = sum;j >= nums[i];j--){
                    dp[j] = dp[j] || dp[j-nums[i]];
                }
            }
            return dp[sum];
        }
        
        public boolean canPartition(int[] nums) {
            int sum = 0;
            for (int item : nums){
                sum += item;
            }
            
            //如果数组元素和不是2的倍数,直接返回false
            if (sum % 2 != 0)
                return false;
            
            return knapSack(nums,sum/2);
        }
    }
    
    展开全文
  • 背包问题总结

    千次阅读 多人点赞 2018-09-13 09:40:11
    前面是转载来的背包9讲,非常详细,后面有几个lintcode上的题目 前言 本篇文章是我(dd_engi)正在进行...背包问题是一个经典的动态规划模型。它既简单形象容易理解,又在某种程度上能够揭示动态规划的本质,故不少...
  • 背包问题

    千次阅读 2019-07-08 22:17:40
    #include <iostream> #include <vector> #include "a_arrayAndMatrix.h" using namespace std; vector<bool> knasSack(int n, int c, int *wight, int *value);... int *weight ...
  • 01背包问题

    2020-10-14 22:12:01
    01背包问题 之间觉得这种DP基础题应该掌握的没问题,leetcode上也没找到这个题,后来在Acwing上做了一下,发现一遍过还是有问题,记录一下,留作复习。 题目 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一...
  • [C语言]背包问题

    万次阅读 2012-09-01 02:11:36
    0-1背包问题   参考: http://blog.csdn.net/liwenjia1981/article/details/5725579 http://blog.csdn.net/dapengbusi/article/details/7463968 动态规划解法 借个图 助于理解 从背包容量为0开始,1号物品先...
  • 背包问题汇总

    万次阅读 2020-04-28 09:28:09
    目录 1. 背包问题 I ——0-1背包无价值 ...3. 背包问题III —— 完全背包问题 小结1 4. 背包问题IV /V ——求方案数 5. 背包问题VII —— 多重背包问题 6. 多重背包可行性解 7. 换零钱问题 1. 背...
  • 01背包问题 图解+详细解析 (转载)

    万次阅读 多人点赞 2020-07-19 00:11:06
    (原文写的非常棒,算法...有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和? 为方便讲解和理解,下面讲述的例子均先用具体的数字代入,即:eg:number=4,cap...
  • 背包问题及其变型(python)

    千次阅读 2018-10-29 22:27:14
    一个背包,往里装东西,重量w(weight)分别为为[2,3,4,5] 价值v(value)对应为[3,4,5,6] 如果你的容量为8,每个物品只有一个,求你能装入背包的最大价值 我们可以一步一步来 ,先创建一个表格 (数组), 数组dp[i][j] i...
  • 背包问题详解:01背包、完全背包、多重背包

    万次阅读 多人点赞 2017-03-17 11:49:07
    参考链接: http://www.cnblogs.com/fengty90/p/3768845.html http://blog.csdn.net/mu399/article/details/7722810 http://blog.csdn.net/xiaowei_cqu/article/details/8191808 ...
  • 多维多选的背包问题

    万次阅读 2017-11-12 15:47:18
    0-1背包问题是一类典型的组合优化问题,它要求找出n个物体的一个子集使其尽可能的装满容量为W的背包。他本质上是一个只有一个约束条件的0-1规划问题,在计算理论上属于NP完全问题,计算复杂性为o(2^n)。随着该问题的...
  • leetcode中完全背包问题集合

    万次阅读 2018-06-29 16:00:33
    发现很多动态规划的题目怎么想都很难出递推公式,而看答案往往都感觉是精巧设计的,但是遇到类似的题目又不知从何下手,看了一天的博客和其他资料,发现这种类型的题目都是一类经典问题的变种:背包问题背包问题主要...
  • 01背包问题的动态规划解法递归方程为: 当 j &gt;= wi 时, m(i, j) = max { m(i-1, j), m(i-1, j-wi) + vi }; 当 j &lt; wi 时, m(i, j) = m(i-1, j) 此时时间复杂度为O(n) 回溯法 使用回溯法解决01...
  • 一个NP完全问题,如果能找到它的多项式时间解
  • 多重背包问题

    万次阅读 多人点赞 2018-08-23 12:19:01
    #include &lt;bits/stdc++.h&gt; using namespace std; struct E { int w; //体积 int v; //重量 } lis[2001]; int dp[101]; int main() { int T,n,m; int p,h,k;... int...
  • 01背包问题(动态规划)python实现

    万次阅读 2014-05-22 20:54:01
    在01背包问题中,在选择是否要把一个物品加到背包中,必须把该物品加进去的子问题的解与不取该物品的子问题的解进行比较,这种方式形成的问题导致了许多重叠子问题,使用动态规划来解决。n=5是物品的数量,c=10是...
  • 【算法】----贪心算法(背包问题

    万次阅读 多人点赞 2013-11-11 21:24:19
     给定n个物品和一个容量为C的背包,物品i的重量是Wi,其价值为Vi,背包问题是如何选择入背包的物品,使得装入背包的物品的总价值最大,注意和0/1背包的区别,在背包问题中可以将物品的一部分装入背包,但不能重复装入...
  • 背包问题引用书上关于0-1背包和部分背包的阐述: 二.贪心与动态规划区别关于红色矩形部分解释为什么0-1不能使用贪心算法,是因为当你选择一个物品时,整个物品的大小都需要计算,然而背包的的大小又是固定的,...
1 2 3 4 5 ... 20
收藏数 64,604
精华内容 25,841
关键字:

背包问题