01 背包
二维数组
递推公式
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v] + w);
自底向上递推
// 自底向上递推
int dp[][] = new int[n + 2][V + 1];
for(int i = n; i >= 1; i--) {
for(int j = 0; j <= V; j++) {
if(j < v[i])
dp[i][j] = dp[i + 1][j]; // 不选
else
dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j - v[i]] + w[i]);
}
}
System.out.print(dp[1][V]);
自顶向下递推
// 自顶向下递推
int dp[][] = new int[n + 1][V + 1];
for(int i = 1; i <= n; i++) { // 第i件物品
for(int j = 0; j <= V; j++) { // 剩余体积为j 时
if(j < v[i]) // 剩余体积<当前物品
dp[i][j] = dp[i - 1][j]; // 不选
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]); // 选与不选 最大者
}
}
System.out.print(dp[n][V]); // 自顶向下
一维滚动数组
// 滚动数组
// 下标体积 值总价值, 省去n编号
int dp[] = new int[V + 1];
for(int i = n; i >= 1; i--) {
// 剩余数量需 从大到小循环
// 这样 dp[j - v[i]] 时的值(未更新) 是上一件物品的最大价值
for(int j = V; j >= v[i]; j--) {
// 不选 选
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
}
System.out.print(dp[V]);
完全背包
递推公式
dp[i][j] = Math.max(dp[i][j], dp[i][j - v] + w );
int dp[][] = new int[n + 1][V + 1];
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= V; j++) {
if(j < v[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i]] + w[i]);
}
}
System.out.print(dp[n][V]);
结论:
- 与01背包区别就是 每种物品都有无限件可用
- 只需将代码中体积循环的 顺序反过来即可
int dp[] = new int[V + 1];
for(int i = 1; i <= n; i++)
for(int j = v[i]; j <= V; j++)
// 选择当前物品时 dp[j - v[i]]已更新 = dp[i][j - v[i]] 而不是第i-1物品的dp
// 含义是 再选一次当前物品(前面可能已选过)
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
System.out.print(dp[V]);
多重背包
递推公式
// 完全背包基础上进行修改
// 不选 选k个
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i] * k] + w[i] * k);
二维数组
int dp[][] = new int[n + 1][V + 1];
for(int i = 1; i <= n; i++)
for(int j = 0; j <= V; j++)
// 选择 k个 i物品
for(int k = 0; k <= s[i] && k*v[i] <= j; k++)
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i] * k] + w[i] * k);
System.out.print(dp[n][V]);
滚动数组
int dp[] = new int[V + 1];
for(int i = 1; i <= n; i++)
// 从后往前遍历, 前面的未更新 是上一件物品的dp
for(int j = V; j >= 0; j--)
for(int k = 0; k <= s[i] && k * v[i] <= j; k++)
dp[j] = Math.max(dp[j], dp[j - v[i] * k] + w[i] * k);
System.out.print(dp[V]);
二进制优化
思路
- 如果要拿1001次苹果,传统就是要拿1001次;二进制的思维,就是拿7个箱子就行
(分别是装有 489[1024 - 512]、256、128、64、32、8、1 个苹果的这7个箱子) 2的k次方
这样一来,1001次操作就变成7次操作就行了。
-
原始滚动数组 时间复杂度
NVS
-
二进制优化 :
NV log(S)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// log2000 约等于 12
// s个物品 拆分成 log(S)
int S = 12;
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int V = sc.nextInt();
int v[] = new int[n * S]; //
int w[] = new int[n * S];
int cnt = 0; // 记录数组下标 从1开始
for(int i = 1; i <= n; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int s = sc.nextInt();
// 每接收一种物品进行拆分
int k = 1; // 2的一次方开始
while(k <= s) {
v[++cnt] = a * k;
w[cnt] = b * k;
s -= k; // 更新件数
k *= 2;
}
if(s > 0) { // 还有剩余件数
v[++cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt; // 最终数组长度
int dp[] = new int[V + 1];
for(int i = 1; i <= n; i++)
for(int j = V; j >= v[i]; j--)
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
System.out.print(dp[V]);
}
}
分组背包
注意 同一组内 只选一个 需先循环体积
- 先循环分组中每一个物品的话, 若同一个组里面有两个物品,
在更新该组第二个物品的时候 dp状态就是包括第一个物品的状态了. 这样就做不到一组只选一个了。
int dp[] = new int[V + 1];
for(int i = 1; i <= n; i++) // 循环分组
for(int j = V; j >= 0; j--) // 循环剩余体积
for(int k = 0; k < s[i]; k++) // 循环分组中每一件物品
if(v[i][k] <= j) // 这里先循环体积, 需加判断
dp[j] = Math.max(dp[j], dp[j - v[i][k]] + w[i][k]);
System.out.print(dp[V]);