动态规划(背包问题)
2019-06-18 本文已影响0人
RalapHao
- 记录局部最优解,作为下次求解的基础
- 重要公式
w[i] > j: v[i][j] = v[i][j];
w[i] <= j : v[i][j] = Math.max(v[i][j], v[i][j - w[i]] + val[i]);
public class KnapsackProblem {
public static void main(String[] args) {
KnapsackProblem kp = new KnapsackProblem();
kp.knapsack();
}
public void knapsack() {
int[] w = {1, 4, 3};
int[] val = {1500, 3000, 2000};
int m = 4;
int n = w.length;
int[][] v = new int[n + 1][m + 1];
for (int i = 0; i < v.length; i++) {
v[i][0] = 0;
}
for (int i = 0; i < v[0].length; i++) {
v[0][i] = 0;
}
for (int i = 1; i < v.length; i++) {
for (int j = 1; j < v[0].length; j++) {
if (w[i - 1] > j) {
v[i][j] = v[i - 1][j];
} else {
v[i][j] = Math.max(v[i - 1][j], v[i - 1][j - w[i-1]] + val[i-1]);
}
}
}
for (int i = 0; i < v.length; i++) {
for (int j = 0; j < v[0].length; j++) {
System.out.print(v[i][j] + " ");
}
System.out.println();
}
}
}