背包概念
01背包问题
有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weights[i],得到的价值是value[i]。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。
输入:weight [1,3,4] value:[15,20,30],最多能背重量总和为4的物品。
dp[i][j]
指的是在[0,i]
个物品中在容量为j的背包中可选择的最大价值。如果当前容量是小于
weight[i]
,那么表示放不下第i
个物品,所以dp[i][j] = dp[i - 1][j];
如果当前容量是大于
weight[i]
,那么表示可以放下第i
个物品,所以当前最大价值等于放这个物品的最大价值dp[i - 1][j - weight[i]] + value[i]
和不放这个物品dp[i - 1][j]
的最大价值。
public class Pack1 {
public static void main(String[] args) {
int[] weight = {
1, 3, 4};
int[] value = {
15, 20, 30};
int bagSize = 4;
System.out.println(testWeightBagProblem(weight, value, bagSize));
}
private static int testWeightBagProblem(int[] weight, int[] value, int bagSize) {
int size = weight.length;
int[][] dp = new int[size][bagSize + 1];
for (int i = weight[0]; i <= bagSize; i++) {
dp[0][i] = value[0];
}
for (int i = 1; i < size; i++) {
for (int j = 1; j <= bagSize; j++) {
if (j < weight[i]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}
return dp[size - 1][bagSize];
}
}
一维思路
为啥不能
int j = weight[i]; j <= bagSize; j++
,是因为想要的是上一轮的数据。当i-1
变成i
的时候,计算dp[j]
的时候,希望dp[j - weight[i]]
是在当前轮次没有计算过的,是dp[i-1][j-weight[i]]
。如果j
从小到大计算,当计算到最大值的时候,dp[j-weight[i]]
已经计算过了,更新成了dp[i][j-weight[i]]
。
private static int testWeightBagProblem2(int[] weight, int[] value, int bagSize) {
int size = weight.length;
int[] dp = new int[bagSize + 1];
for (int i = 0; i < size; i++) {
for (int j = bagSize; j >= weight[i]; j--) {
// for (int j = weight[i]; j <= bagSize; j++) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[bagSize];
}
完全背包
完全背包是物品有无数个,可以选几个也可以不选。
如何去理解,01背包从后往前,完全背包从前往后遍历。从后往前获取的永远是
dp[i-1][j]
的数据,是没有第i
个物品的情况下的计算结果。所以dp[j]
的计算结果总是物品只能选择单个。
public class Pack2 {
public static void main(String[] args)