背包问题——动态规划——Java实现

背包问题

动态规划实现

动态规划：本质上是枚举（不重复的暴力枚举），因此其复杂度很好分析，有多少个状态就要被计算多少次，复杂度就为多少。

public class Knapsack {
public static void main(String[] args) {
int n = 5;
int c = 10;
int[] w = new int[]{2, 2, 6, 5, 4};
int[] v = new int[]{6, 3, 5, 4, 6};
Knapsack knapsack = new Knapsack();
int[][] res = knapsack.bag(n, c, w, v);
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < c + 1; j++) {
System.out.print(res[i][j] + " ");
}
System.out.println();
}
knapsack.show(n, c, w, res);
}
public int[][] bag(int n, int c, int[] w, int[] v) {
int[][] res = new int[n + 1][c + 1];
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < c + 1; j++) {
res[i][j] = res[i - 1][j];
if (j >= w[i - 1] && res[i - 1][j - w[i - 1]] + v[i - 1] > res[i][j]) {
res[i][j] = res[i - 1][j - w[i - 1]] + v[i - 1];
}
}
}
return res;
}
public void show(int n, int c, int[] w, int[][] res) {
System.out.println("最大价值为：" + res[n][c]);
boolean[] x = new boolean[n];
int j = c;
for (int i = n; i > 0; i--) {
if (res[i][j] > res[i - 1][j]) {
x[i - 1] = true;
j -= w[i - 1];
}
}
System.out.println("选择的物品为：");
for (int i = 0; i < n; i++) {
if (x[i]) {
System.out.println("第 " + i + " 个");
}
}
System.out.println();
}
}

最后

以上就是故意樱桃为你收集整理的背包问题——动态规划——Java实现的全部内容，希望文章能够帮你解决背包问题——动态规划——Java实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。