小明有一个容量为V的背包。
这天他去商场购物,商场一共有N件物品,第i件物品的体积为wi,价值为v_i。
小明想知道再购买的物品总体积不超过V的情况下所能获得的最大价值为多少,请你帮他算算。
输入描述
输入第1行包含两个正整数N,V,表示商场物品的数量和小明的背包容量。
第2~ N+1行每行包含两个正整数w,v,表示物品的体积和价值。
输出描述
输出一行整数表示小明所能获得的最大价值。
输入输出样例
输入
5 20
1 6
2 5
3 8
5 15
3 3
输出
37
我们用一个简单的实例去分析,我们假设当前物品描述如下:
物品编号 | 1 | 2 | 3 | 4 |
---|---|---|---|---|
重量 | 2 | 3 | 4 | 5 |
价值 | 3 | 4 | 5 | 8 |
我们有4件物品,背包容量为8,我们的目标是求在背包容量为8的前提下能装物品的最大价值。
定义f(k,w)
为:当背包容量为w,现在有k件物品可以偷,所能偷到的最大价值。
所以我们的目标就是求f(4,8)
分析如下:
上图中带√表示选了第k件物品,×表示没选第k件物品。
如果拿了第4件物品,那么f(4,8)就转化为拿了前3件物品的情况,此时
如果没拿第4件物品,那么
,因为没拿第4件,所以背包容量没变,也不用再加第4件物品的价值。
得出状态转移方程:
当
时,
代表没拿第k件物品,
代表拿了第k件物品。
我们可以将所有的计算结果写成表格。
物品编号\背包容量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1:w=2,v=3 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
2:w=3,v=4 | 0 | 0 | 3 | 4 | 4 | 7 | 7 | 7 | 7 |
3:w=4,v=5 | 0 | 0 | 3 | 4 | 5 | 7 | 8 | 9 | 9 |
4:w=5,v=8 | 0 | 0 | 3 | 4 | 5 | 8 | 8 | 11 | 12 |
这里f(0,w)表示不拿物品,价值肯定为0,f(k,0)表示被包装量为0,肯定装不下,所以第一行和第一列都是0,这里算几个关键的。
这里只给出一部分的计算过程,其他的类似
import java.util.Scanner;
//小明的背包
public class Bag {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int N = scan.nextInt(); //物品数量
int V = scan.nextInt(); //背包容量
int[] w = new int[N + 1];//物品体积
int[] v = new int[N + 1];//物品价值
//记录最优解,我们的目标是f[N][V]
int[][] f = new int[N + 1][V + 1];
for (int i = 1; i <=N; i++) {
w[i]=scan.nextInt();
v[i]=scan.nextInt();
}
for (int i = 1; i <=N; i++) { //i代表N件物品
for (int j = 1; j <=V; j++) { //j表示背包容量
if(w[i]>j){ //太重,装不下
f[i][j]=f[i-1][j];
}else{
//f[i][j]=max{不拿第i件,拿第i件}
f[i][j]=Math.max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
}
}
}
System.out.println(f[N][V]);
}
}