简单0-1背包问题求解
简单0-1背包问题求解
1、题目描述
小明有一个容量为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输出
372、示例分析
我们用一个简单的实例去分析，我们假设当前物品描述如下：
物品编号 | 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，这里算几个关键的。
这里只给出一部分的计算过程，其他的类似
3、代码实现
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]);
}
}