完全背包问题
动态规划
完全背包问题相对于01背包问题改变的就是第$i$个物品选取的数量,01背包最多就只能选一个,而完全背包只需要在体积允许的条件下选取任意个数,然后取$max$即为只从前$i$个物品中选且总体积不超过$j$的集合的最大值。
数组:$f[i][j]$
状态转移方程:$f[i][j] = max\{f[i][j], f[i - 1][j - k * v[i]] + k * w[i]\}$ $(k从0开始枚举)$
$Java$ 代码
import java.util.*;
public class Main {
static final int N = 1010;
static int[] v = new int[N], w = new int[N];
static int[][] f = new int[N][N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
for (int i = 1; i <= n; i ++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
for (int k = 0; k * v[i] <= j; k ++) {
f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
}
}
}
System.out.print(f[n][m]);
}
}
优化时间
我们发现,上述的算法时间复杂度比较高,有3重循环,那么我们来考虑是否可以优化。
从$f[i][j]与f[i][j - v]$的关系出发,看能否推导除直接的关系,那么就可以省略$k$这一层的循环了。
$f[i][j] = max\{f[i - 1][j], f[i - 1][j - v] + w, f[i - 1][j - 2v] + 2w, …, f[i - 1][j - k_1v] + k_1w\}$
$f[i][j - v] = max\{f[i - 1][j - v], f[i - 1][j - 2v] + w, …, f[i - 1][j - (v + k_2v)] + k_2w\}$
由$k_1, k_2$的含义可知,$k_1v = j$, $v + k_2v = j$, 所以化简得$k_1 = k_2 + 1$。
故,$f[i][j - v] = max\{f[i - 1][j - v], f[i - 1][j - 2v] + w, …, f[i - 1][j - (v + (k_1 - 1)v)] + (k_1 - 1)w\}$
我们可以惊奇地发现,$f[i][j - v]$与$f[i][j]$除去第一项的其他部分,每一项之差为$w$,所以,
$f[i][j] = max\{f[i - 1][j], f[i][j - v] + w\}$
$Java$ 代码
import java.util.*;
public class Main {
static final int N = 1010;
static int[] v = new int[N], w = new int[N];
static int[][] f = new int[N][N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
for (int i = 1; i <= n; i ++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = Math.max(f[i - 1][j], f[i][j - v[i]] + w[i]);
}
System.out.print(f[n][m]);
}
}
进一步优化空间
这里优化空间的思路同01背包,只是枚举$j$的顺序是从小到大,01背包是从大到小(需要理解原理)。
import java.util.*;
public class Main {
static final int N = 1010;
static int[] v = new int[N], w = new int[N], f = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
for (int i = 1; i <= n; i ++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
for (int i = 1; i <= n; i ++)
for (int j = v[i]; j <= m; j ++) {
f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
}
System.out.print(f[m]);
}
}