`
wangqisen
  • 浏览: 46429 次
文章分类
社区版块
存档分类
最新评论

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]]的值。伪代码如下:

fori=1..N

forv=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分别表明这件物品的费用和价值。

procedureZeroOnePack(cost,weight)

forv=V..cost

f[v]=max{f[v],f[v-cost]+weight}

注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成v=V..0是为了在程序中体现每个状态都按照方程求解了,避免不必要的思维复杂度。而这里既然已经抽象成看作黑箱的过程了,就可以加入优化。费用为cost的物品不会影响状态f[0..cost-1],这是显然的。

有了这个过程以后,01背包问题的伪代码就可以这样写:

fori=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背包问题求解。故一定要仔细体会上面基本思路的得出方法,状态转移方程的意义,以及最后怎样优化的空间复杂度。




以上内容来自背包九讲。

下面是,我自己写的一段实现最基本的01背包问题的算法过程。

input:n表示物品的种类数,v表示背包容量,weight是每种物品的重量,value则是其价值。

#include<iostream>
using namespace std;
#define NUMMAX 10000
int max(int i,int j);
int main(){
	int weight[NUMMAX],value[NUMMAX],n,v,i=0,j=0;
	int f[NUMMAX];
	while(true){
		cin>>n>>v;
		for(i=0;i<NUMMAX;i++)
			f[i]=0;
		for(i=0;i<n;i++)
			cin>>weight[i]>>value[i];
		for(i=0;i<n;i++){
			for(j=v;j>=0;j--){
				if(j>=weight[i])
					f[j]=max(f[j],f[j-weight[i]]+value[i]);
			}
		}
		cout<<f[v]<<endl;
	}
}
int max(int i,int j){
	if(i>=j)
		return i;
	else
		return j;
}


分享到:
评论

相关推荐

    遗传算法解决01背包问题分析及代码

    01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下: 给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择...

    c c++ 01背包问题动态规划解决

    01背包问题解决方法不少,动态规划是其中之一,动态规划的问题解题思路都差不多(一些浅见),基本要素是最优子结构性质,子问题重叠性质,自底向上的求解方法。只要了解了基本要素,那么这种题型也会更好理解。本题...

    遗传算法求解01背包问题——问题分析

    01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下: 给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择...

    动态规划解决01背包问题

    01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2至Wn,与之相对应的价值为P1,P2至Pn。01背包是背包问题中最简单的问题。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,...

    遗传算法0-1背包问题论文

    01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下: 给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择...

    基础背包问题和01背包问题

    1)一个简化的背包问题:一个背包能装总重量为 tota1_m,现有 n 个物件,其重量分别为(W1、W2、…、Wn)。问能否从这 n 个物件中挑选若干个物件放入背包中,使其总重量正好为 T ?...3)01背包问题

    01背包测试数据

    注意的一点是,背包内的物品的重量之和不能大于背包的容量C。在选择装入背包的物品时,对每种物品i只有两种选择:装入背包或者不装入背包,即只能将物品i装入背包一次。称此类问题为0/1背包问题。

    0 1 背包问题 分支界限 回溯+剪枝

    问题描述:给定一个容量为C的背包及n个重量为wi,价值为p1的物品,要求把物品装入背包,是背包的价值最大,此类问题为背包问题。物品或者装入背包,或者不装入背包,称之为0/1被包问题 假设xi表示物品i被装入背包的...

    模拟退火算法解决0-1背包问题的实现

    背包问题,是指从n件不同价值、不同重量物品中按一定的要求选取一部分物品,并使选中物品的价值之和为最大的问题。其形式化描述如下:给定一个物品集合s={1,2,…,n},物品i具有重量 和价值 。背包能承受的最大载重...

    用分枝界限 回溯+剪枝 动态规划 解决01背包问题

    问题描述:给定一个容量为C的背包及n个重量为wi,价值 为p1的物品,要求把物品装入背包,是背包的价值最大, 此类问题为背包问题。物品或者装入背包,或者不装入背 包,称之为0/1被包问题 假设xi表示物品i被装入背包...

    01背包问题 动态规划问题.zip

    这种情况,我们称之为0-1背包问题。而如果我们可以使用部分的物品的话,这个问题则成为部分背包(fractional knapsack)问题。 三、数据与问题 有5个物品,其重量分别是{2, 2, 6, 5, 4},价值分别为{6, 3, 5, 4, 6},...

    算法分析与设计实验报告利用回溯算法解决背包问题

    算法分析与设计实验报告书:回溯算法之背包问题。 实验目的和要求 (1)掌握回溯法的设计思想; (2)掌握解空间树的构造方法,以及在求解过程中如何存储求解路径; (3)考察回溯法求解问题的有效程度。 (4)设计...

    0—1背包问题的动态规划法及回溯法

    设有一个背包可以放入的物品重量为S,现有n件物品,重量分别是w1,w2,w3,…wn。 问能否从这n件物品中选择若干件放入背包中,使得放入的重量之和正好为S。 如果有满足条件的选择,则此背包有解,否则此背包问题无...

    动态规划 01背包问题 c++代码

    动态规划之01背包问题,cpp示例代码,经测试,编译通过,可直接使用。 背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,...

    背包之01背包、完全背包、多重背包详解1

    1. 描述一个最优解的结构 2. 递归地定义最优解的值 3. 以“自底向上”的方式计算最优解的值 4. 从已计算的信息中构建出最优解的路径

    Leetcode经典01背包-leet:LeetCode刷题走起~

    Leetcode经典01背包 LeetCode 刷题走起~ _ _ \ | | ___ ___| |_ . ___________| | / _ \/ _ \ __|____|_._._._._. `——————————| |__| __/ __/ |_ ————|—*—*—*—*—| / |_____\___|\___|\__| l 题型...

    经典动态规划合集_牛人 树形,压缩 老题

    背包之01背包、完全背包、多重背包详解 Dynamic+Programming 典型的动态规划,用递归下的记忆化搜索来实现 1088 POJ 动态规划加速原理之四边形不等式 基于连通性状态压缩的动态规划问题 对一些DP题目的小结 树型动态...

    KnapsackProblem

    在01背包问题中,我们得到了一个容量为C的背包。我们还得到了N个对象的列表,每个对象的权重为W(I),利润为P(I)。 只要选择的总重量不超过C,我们就可以将对象的任何子集放入背包。我们希望使总利润最大化,这是...

    leetcode推箱子-dynamic-planning:动态规划

    背包问题:01背包问题,完全背包问题,分组背包问题,二维背包,装箱问题,挤牛奶(同济ACM第1132题)等; 应用实例: 最短路径问题 ,项目管理,网络流优化等; 给定一个整数数组,找到一个具有最大和的子数组,...

    leetcode76-Hihocode:Hihocode经典算法问题

    01背包 1043 完全背包 1306 股票价格 1318 非法二进制数(数位dp) 1469 福字 计算几何 1040 矩形判断 树 1049 后续遍历 1062 最近公共祖先·一(LRC) 1325 平衡树·Treap AC 图 1066 无间道之并查集(并查集) 1307 ...

Global site tag (gtag.js) - Google Analytics