package com.xiejianjun.day12;
import java.util.Arrays;
/**
* @author bilibilidick
* @version 2022 04
* @date 2022/4/28 15:36
*/
public class _01Backpack {
//物品质量
private final int[] w = {1, 4, 3};
//物品价值
private final int[] v = {1500, 3000, 2000};
//背包容量
private final int backpackV = 4 ;
//总价值二维数组
private int[][] dp;
public void displayDpArr() {
if (dp == null) return;
for (int[] ints : dp) {
System.out.println(Arrays.toString(ints));
}
int i = dp.length - 1;
int j = dp[0].length - 1;
while (i > 0) {
// if (result[i][j] == 1) {
if (dp[i][j] != dp[i - 1][j]) {
System.out.println("序号" + i + "的物品已放入背包中");
j -= w[i - 1];
}
else {
System.out.println("序号" + i + "的物品未放入背包中");
}
i--;
}
}
public void getDp() {
init();
for (int i = 1; i <= w.length; i++) {
for (int j = 0; j < backpackV + 1; j++) {
if (w[i - 1] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
}
}
}
}
private void init() {
this.dp = new int[w.length + 1][backpackV + 1];
for (int i = 0; i < w.length + 1; i++) {
for (int j = 0; j < backpackV + 1; j++) {
dp[i][j] = 0;
}
}
}
public static void main(String[] args) {
_01Backpack backpack = new _01Backpack();
backpack.getDp();
backpack.displayDpArr();
}
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)