原文地址:http://blog.csdn.net/zs234/article/details/7487960
背包问题(Knapsackproblem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。这个问题涉及到了两个条件:一是物品总的大小小于或等于背包的大小,二是物品总的价值要尽量大。
如果我们用子问题定义状态来描述的话可以这样解释:
用f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。用公式表示:
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}或 f[v]=max{f[v],f[v-c[i]]+w[i]}
具体的解释可以理解为将前i件物品放入容量为v的背包中,现只考虑第i件物品的策略(放或不放),那么就可以转化为一个只涉及前i-1件物品和第i件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为f[i-1][v];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。(v表示背包的最大容量,c[i]表示第i件物品的大小,w[i]表示第i件物品的价值)
算法如下:
程序运行的过程如下:
i=0时,放入李子
背包负重 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
s |
- |
- |
- |
4 |
5 |
6 |
7 |
8 |
p |
- |
- |
- |
0 |
1 |
2 |
3 |
4 |
value |
0 |
0 |
0 |
4500 |
4500 |
4500 |
4500 |
9000 |
item |
- |
- |
- |
0 |
0 |
0 |
0 |
0 |
i=1时,放入苹果
背包负重 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
s |
- |
- |
- |
- |
5 |
6 |
7 |
8 |
p |
- |
- |
- |
- |
0 |
1 |
2 |
3 |
value |
0 |
0 |
0 |
4500 |
5700 |
5700 |
5700 |
9000 |
item |
- |
- |
- |
0 |
1 |
1 |
1 |
0 |
i=2时,放入橘子
背包负重 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
s |
- |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
p |
- |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
value |
0 |
2250 |
2250 |
4500 |
5700 |
6750 |
7950 |
9000 |
item |
- |
2 |
2 |
0 |
1 |
2 |
2 |
0 |
i=3时,放入草莓
背包负重 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
s |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
p |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
value |
1100 |
2250 |
3350 |
4500 |
5700 |
6800 |
7950 |
9050 |
item |
3 |
2 |
3 |
0 |
1 |
3 |
2 |
3 |
i=4时,放入甜瓜
背包负重 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
s |
- |
- |
- |
- |
- |
6 |
7 |
8 |
p |
- |
- |
- |
- |
- |
0 |
1 |
2 |
value |
1100 |
2250 |
3350 |
4500 |
5700 |
6800 |
7950 |
9050 |
item |
3 |
2 |
3 |
0 |
1 |
3 |
2 |
3 |
由最后一个表格可以知道,在背包负重8的时候,最多得到价值9050的水果,这个时候可以得到装入的水果是3号水果草莓,那么剩下的(8-1=7)个大小空间,可以知到为2号水果也就是橘子,同理下一步可以知道放入的水果是1号水果苹果。此时获得的最优解的价值就是9050,放入的水果是草莓、橘子和苹果。
到此,我们的背包问题已经解决,要了解上述算法,需要读者分析出背包算法中的每一步都做了什么操作,这一点可以通过上述的表格看出,希望本文对读者理解背包算法有所帮助!
相关推荐
01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下: 给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择...
实验目的:0/1背包问题的回溯算法设计 实验原理:回溯算法设计。 实验要求:基本掌握回溯算法设计的原理方法。熟练掌握VC++中编程实现算法的常用技术和方法。 算法思想: 0-1背包问题:给定n种物品和一背包.物品i的...
《背包问题九讲》,dd_engi大神...目录:1、01背包问题;2、完全背包问题;3、多重背包问题;4、混合三种背包问题;5、二维费用背包问题;6、分组的背包问题;7、有依赖的背包问题;8、泛化物品;9、背包问题的变化;
背包问题的一种解决办法 用递归枚举解决与利润无关背包问题 不是自己创作 文件中的函数名称和简单功能描述: Cbeibao1_0::input():输入关于背包问题的数据信息(背包总重量total_weight,物品件数number, ...
贪心算法 背包问题 c语言 绝对无误 运行成功
背包问题(Knapsack problem)是组合优化领域的一类经典问题: 给定一个物品集合,每个物品具有一定重量以及一定的价值. 对于一个承载重量有限的背包,如何决定放入的物品,使得在背包承载的范围内获取所装物品的最大...
0-1背包问题测试数据,内含多组测试数据,物品的价值量及其重量,复制粘贴即可使用
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最...
简单的遗传算法用于解决背包问题codeblocks编写,运行成功
【背包问题】基于遗传算法求解多背包问题matlab源码
背包问题,算法的背包问题 背包问题,算法的背包问题 背包问题,算法的背包问题
C语言数据结构经典作业 背包问题求解 用栈与非递归算法实现的
此文章讲述了经典的背包问题,以及各种背包问题的变种,是学习算法比较好的东西,也有助于学习各种思想,进一步提高我们解决问题的能力
功能:用贪婪法解决连续背包问题 文件中的函数名称和简单功能描述: Cbeibao2::input():输入关于背包问题的数据信息(背包总重量total_weight,物品件数number, 及每个物品的重量和价值),并为成员指针...
第一讲 01背包问题 这是最基本的背包问题,每个物品最多只能放一次。 第二讲 完全背包问题 第二个基本的背包问题模型,每种物品可以放无限多次。 第三讲 多重背包问题 每种物品有一个固定的次数上限。 第四讲 ...
背包问题: 01背包问题 02: 完全背包问题 03: 多重背包问题 04: 混合三种背包问题 05: 二维费用的背包问题 06: 分组的背包问题 07: 有依赖的背包问题 08: 泛化物品 09: 背包问题问法的变化 11: 背包问题的搜索解法
与0-1背包问题类似,所不同的是在选择物品i装入背包时,可以选择物品i的一部分,而不一定要全部装入背包,1≤i≤n。
用禁忌搜索算法求解背包问题。假设背包容量一定,已知每种物品的体积和价值,求出使价值最大的最优解。
主要介绍了Python基于回溯法解决01背包问题,结合实例形式分析了Python回溯法采用深度优先策略搜索解决01背包问题的相关操作技巧,需要的朋友可以参考下
在中国,背包问题一般是这样描述的:设n个重量为(W1,W2,...Wn)的物品和一个载重为S的背包,将物品的一部分xi放进背包中的利润是Pixi,问如何选择物品的种类和数量,使得背包装满而获得最大的利润?另有一简化版本...