背包问题(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件物品的价值)
算法如下:
class Fruit{
private String name;
private int size;
private int price;
public Fruit(String name,int size,int price){
this.name=name;
this.size=size;
this.price=price;
}
public String getName(){
return name;
}
public int getPrice(){
return price;
}
public int getSize(){
return size;
}
}
public class Knapsack{
public static void main(String[] args){
final int MAX=8;
final int MIN=1;
int[] item=new int[MAX+1];
int[] value=new int[MAX+1];
Fruit fruits[]={
new Fruit("李子",4,4500),
new Fruit("苹果",5,5700),
new Fruit("橘子",2,2250),
new Fruit("草莓",1,1100),
new Fruit("甜瓜",6,6700)
};
for(int i=0;i<fruits.length;i++){
for(int s=fruits[i].getSize();s<=MAX;s++){//s表示现在背包的大小
int p=s-fruits[i].getSize();//表示每次增加单位背包空间,背包所剩的空间
int newvalue=value[p]+fruits[i].getPrice();//value[p]表示增加的背包空间可以增加的价值,fruits[i].getprice()表示原有的背包的价值
if(newvalue>value[s]){//现有的价值是否大于背包为s时的价值
value[s]=newvalue;
item[s]=i;//将当前的水果项添加到背包的物品中
}
}
}
System.out.println("物品\t价格");
for(int i=MAX;i>MIN;i=i-fruits[item[i]].getSize()){
System.out.println(fruits[item[i]].getName()+
"\t"+fruits[item[i]].getPrice());
}
System.out.println("合计\t"+value[MAX]);
}
}
程序运行的过程如下:
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背包,多重背包等等
动态规划(DP)——背包问题算法详解[背包九讲]
简单的遗传算法用于解决背包问题codeblocks编写,运行成功
本文详细的分析了贪心算法的背包问题,并且提供的代码。
用贪心算法解决背包问题,用netbeans做的。百分百下载就可以直接运行。JAVA 源文件。
包括回溯法,贪心法,分治法等经典算法,通过具体问题(包括很多经典问题,n皇后问题,迷宫求解,背包问题等)。。。相信肯定有很大用处、、、、、
背包问题
0-1-背包问题与遗传算法 使用遗传算法在 Python 中解决 0-1 背包问题的简单方法
"《Python算法详解》读书笔记模板.pptx" 《Python算法详解》读书笔记模板.pptx是基于Python算法的读书笔记模板,涵盖了Python算法的核心技术和知识点。本书共13章,涵盖了算法、数据结构、常用的算法思想、线性表、...
多重背包O(NV)算法详解(使用单调队列).doc
背包问题 01背包问题和分数背包问题详解(贪心算法) 01背包问题和分数背包问题详解(贪心算法) 01背包问题和分数背包问题详解(贪心算法)
经典算法.pdf 算法举例详解 河内塔 费式数列 巴斯卡三角形 三色棋 老鼠走迷官(一) 老鼠走迷官(二) 骑士走棋盘 八个皇后 八枚银币 生命游戏 字串核对 双色、三色河内塔 背包问题(Knapsack Problem) 数、运算 ...
01背包问题动态规划 01背包问题和分数背包问题详解(动态规划和贪心算法) 01背包问题和分数背包问题详解(动态规划和贪心算法) 01背包问题和分数背包问题详解(动态规划和贪心算法)
回朔法背包问题,经典算法,需要的下
9大背包问题详解
使用动态规划解决经典问题,例如爬楼梯、打家劫舍问题、单词拆分问题、买卖股票问题等 动态规划是一种算法设计技术,它通过将问题分解为重叠的子问题并利用已经解决的子问题的结果来解决更大的问题。 通常用于解决...
介绍动态规划的算法原理,和应用动态规划算法解决背包问题等实际问题的例子。还有解决这些问题的C语言程序,该资料是本校的ACM竞赛培训材料,相信对于大家提高编程能力有用
这是以前在学校学算法设计时写的程序了,都不太记得了。 是0-1背包的回溯算法。 内附实验报告,详解算法设计过程。
背包問題(Knapsack Problem) 數、運算 蒙地卡羅法求 PI Eratosthenes篩選求質數 超長整數運算(大數運算) 長 PI 最大公因數、最小公倍數、因式分解 完美數 阿姆斯壯數 最大訪客數 中序式轉後序式...
0-1背包问题动态规划详解及代码,下载使用,0-1背包问题动态规划详解及代码。