2017-04-24 09:51:30         来源：Carinya的博客

## 求解过程

```public class Knapsack {
private int V[][];
private int P[][];//记录背包中装入的物品序号
private int n;//物品个数
private int v[];//物品价值
private int w[];//物品质量
private int C;//背包容量

private Knapsack(int[] w, int[] v, int C) {
this.w = w;
this.v = v;
this.C = C;
this.n = w.length;
this.V = new int[n + 1][C + 1];
this.P = new int[n + 1][C + 1];
}

private void print(int[][] P) {
int i = n;
int j = C;

System.out.print("装入物品的序号为：");

for (; i > 0 && j > 0; i--) {
if (P[i][j] == 1) {
System.out.print(i + " ");
j -= w[i - 1];
}
}
}

private void knapsack() {

for (int j = 0; j <= C; j++) {
V[0][j] = 0;
}

for (int i = 0; i <= n; i++) {
V[i][0] = 0;
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= C; j++) {
if (w[i - 1] > j) {
V[i][j] = V[i - 1][j];
} else {
if (V[i - 1][j - w[i - 1]] + v[i - 1] > V[i - 1][j]){
V[i][j] = V[i - 1][j - w[i - 1]] + v[i - 1];
P[i][j] = 1;//前i个点的最优解i在背包中
} else {
V[i][j] = V[i - 1][j];
}
}// V[i][j] = Math.max(V[i - 1][j - w[i - 1]] + v[i - 1], V[i - 1][j]);

}
}

for (int i = 0; i <= w.length; i++) {
for (int j = 0; j <= C; j++) {
System.out.print(V[i][j] + " ");
if (j == C) {
System.out.println();
}
}
}
System.out.println("最大价值为：" + V[n][C]);
print(P);
}

public static void main(String[] args) {
int w[] = {3, 5, 2, 6, 4};
int v[] = {4, 4, 3, 5, 3};
int C = 12;
Knapsack k = new Knapsack(w, v, C);
k.knapsack();
}
}
```