输入
测试数据有3行：其第1行上有2个整数n和c，分别是物品个数n和背包所能容纳物品的重量，（n<=50,c<=500），第2行上有n个整数v1、v2、…、vn，依次是n个物品的价值，第3行上有n个整数w1、w2、…、wn,，分别是n个物品的重量。诸整数之间用一个空格分开。
输出
输出具体放物品的最大价值
输入样例
5 10
6 3 5 4 6
2 2 6 5 4
算法思想
我们将在总重量不超过Y的前提下，前j种物品的总价格所能达到的最高值定义为A(j, Y)。
A(j, Y)的递推关系为：
A(0, Y) = 0
A(j, 0) = 0
如果 wj > Y,超过背包容量舍弃， A(j, Y) = A(j - 1, Y)
如果 wj ≤ Y,两种情况，放第j个物品和不放第j个物品， A(j, Y) = max { A(j - 1, Y), pj + A(j - 1, Y - wj) }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
package dynamic.plan;
import java.util.Scanner;
public class Knapsack {
private int[] weight;
private int[] value;
private int pack;
int[][] f;
public void init() {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
pack = in.nextInt();
weight = new int[n+1];
value = new int[n+1];
int i;
for(i=1; i<n+1; i++)
value[i] = in.nextInt();
for(i=1; i<n+1; i++)
weight[i] = in.nextInt();
}
private int _top01PackageAnswer(int n, int w) {
if (n==0 || w==0) {
return 0;
}
if (weight[n] > w) {
return _top01PackageAnswer(n-1, w);
}else {
return Math.max(_top01PackageAnswer(n-1, w), _top01PackageAnswer(n-1, w-weight[n]) + value[n]);
}
}
public void top01PackageAnswer() {
System.out.println(_top01PackageAnswer(weight.length-1, pack));
}
public void buttom01PackageAnswer() {
f = new int[weight.length][pack+1];
int i,j;
for(i=1; i<weight.length; i++){
for(j=0; j<=pack; j++){
if (weight[i] > j) {
f[i][j] = f[i-1][j];
} else {
f[i][j] = Math.max(f[i-1][j], f[i-1][j-weight[i]] + value[i]);
}
}
}
System.out.println(f[weight.length-1][pack]);
StringBuffer str = new StringBuffer();
int x,y;
x = weight.length-1;
y = pack;
while(x > 0 && y>0) {
if (f[x-1][ y-weight[x] ] == f[x][y]-value[x]) {
str.append(","+x);
y -= weight[x];
}
x--;
}
System.out.println(str.reverse().toString());
}
public static void main(String[] args) {
Knapsack k = new Knapsack();
k.init();
k.buttom01PackageAnswer();
}
}
|
在执行自低向上求解时，数组 f 的值如下：
[
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 6, 6, 6, 6, 6, 6, 6, 6, 6],
[0, 0, 6, 6, 9, 9, 9, 9, 9, 9, 9],
[0, 0, 6, 6, 9, 9, 9, 9, 11, 11, 14],
[0, 0, 6, 6, 9, 9, 9, 10, 11, 13, 14],
[0, 0, 6, 6, 9, 9, 12, 12, 15, 15, 15]
]