根据第二维是否是逆序分:
顺序:完全背包、求具体方案
逆序:其他所有
01背包的延申:
01背包只有第三种情况可以为负值
体积 <= m 的权值最大情况:
while (n -- > 0)
for (int j = m; j >= v; j--)
f[j] = Math.max(f[j], f[j - v] + w);
体积 == m:
初始化为不可达,f[0] = 0;
while (n -- > 0)
for (int j = m; j >= v; j--)
f[j] = Math.max(f[j], f[j - v] + w); // 或者min
体积 >= m 的权值最小情况
初始化为不可达,f[0] = 0;
while (n -- > 0)
for (int i = n; i >= 0; i--)
f[i][j] = Math.min(f[i], f[Math.max(0, i - a)] + c);
求方案数
import java.util.Scanner;
import java.util.Arrays;
public class Main {
static final int N = 1010;
static final int mod = (int) 1e9 + 7;
static int[] f = new int[N];
static int[] g = new int[N];
static int n, m;
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
Arrays.fill(f, -0x3f3f3f3f);
f[0] = 0;
g[0] = 1;
for (int i = 1; i <= n; i ++) {
int v = sc.nextInt();
int w = sc.nextInt();
for (int j = m; j >= v; j --) {
int maxv = Math.max(f[j], f[j - v] + w);
int cnt = 0;
if (f[j] == maxv) cnt += g[j];
if (f[j - v] + w == maxv) cnt += g[j - v];
f[j] = maxv;
g[j] = cnt % mod;
}
}
sc.close();
int res = 0;
for (int i = 0; i <= m; i ++)
res = Math.max(res, f[i]);
int cnt = 0;
for (int i = 0; i <= m; i++)
if (f[i] == res)
cnt = (cnt + g[i]) % mod;
System.out.println(cnt);
}
}
多重背包问题
从前i类物品中选,第i种物品选j个的集合
方案一:
for (int i = 0; i < n; i++) {
int v = sc.nextInt();
int w = sc.nextInt();
int s = sc.nextInt();
for (int j = m; j >= v; j--)
for (int k = 0; k <= s && k * v <= j; k++)
f[j] = Math.max(f[j], f[j - v * k] + w * k);
}
方案二(预处理):
int cnt = 0;
for (int i = 1; i <= n; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int s = sc.nextInt();
int k = 1;
while (k <= s) {
cnt++;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if (s > 0) {
cnt ++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt;
for (int i = 1; i <= n; i++)
for (int j = m; j >= v[i]; j--)
f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
分组背包问题
从前i类物品中选,第i种物品选第j个的集合
for (int i = 1; i <= n; i++) {
s[i] = sc.nextInt();
for (int j = 1; j <= s[i]; j++) {
v[i][j] = sc.nextInt();
w[i][j] = sc.nextInt();
}
}
for (int i = 1; i <= n; i++)
for (int j = m; j >= 0; j--)
for (int k = 1; k <= s[i]; k++)
if (v[i][k] <= j)
f[j] = Math.max(f[j], f[j - v[i][k]] + w[i][k]);
混合背包问题
区分是:最后一步的不同
import java.util.Scanner;
public class Main {
static final int N = 1010;
static int[] f = new int[N];
static int n, m;
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i < n; i++) {
int v, w, s;
v = sc.nextInt();
w = sc.nextInt();
s = sc.nextInt();
if (s == 0)
for (int j = v; j <= m; j++) f[j] = Math.max(f[j], f[j - v] + w);
else {
if (s == -1) s = 1;
for (int k = 1; k <= s; k <<= 1) {
for (int j = m; j >= k * v; j--)
f[j] = Math.max(f[j], f[j - k * v] + k * w);
s -= k;
}
if (s > 0) {
for (int j = m; j >= s * v; j--)
f[j] = Math.max(f[j], f[j - s * v] + s * w);
}
}
}
sc.close();
System.out.println(f[m]);
}
}