AcWing 3. 完全背包问题
原题链接
简单
作者:
没有你哪有我
,
2022-04-28 09:52:18
,
所有人可见
,
阅读 132
暴力枚举
时间复杂度:O(nv^2)
空间复杂度:O(nv)
import java.util.*;
public class Main {
static int N = 1000 + 10;
static int[][] f = new int[N][N];
static int n, v;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
v = in.nextInt();
for (int i = 1; i <= n; i++) {
int a = in.nextInt();
int b = in.nextInt();
for (int j = 0; j <= v; j++) {
for (int k = 0; k * a <= j; k++) {
f[i][j] = Math.max(f[i][j], f[i - 1][j - a * k] + b * k);
}
}
}
System.out.println(f[n][v]);
}
}
优化:不需要依次枚举第i个物品所有可能选的数量
时间复杂度:O(nv)
空间复杂度:O(nv)
import java.util.*;
public class Main {
static int N = 1000 + 10;
static int[][] f = new int[N][N];
static int n, v;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
v = in.nextInt();
for (int i = 1; i <= n; i++) {
int a = in.nextInt();
int b = in.nextInt();
for (int j = 0; j <= v; j++) {
f[i][j] = f[i - 1][j];
if (j >= a) {
f[i][j] = Math.max(f[i][j], f[i][j - a] + b);
}
}
}
System.out.println(f[n][v]);
}
}
优化:空间由二维变为一维
时间复杂度:O(nv)
空间复杂度:O(n)
import java.util.*;
public class Main {
static int N = 1000 + 10;
static int[] f = new int[N];
static int n, v;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
v = in.nextInt();
for (int i = 1; i <= n; i++) {
int a = in.nextInt();
int b = in.nextInt();
for (int j = a; j <= v; j++) {
f[j] = Math.max(f[j], f[j - a] + b);
}
}
System.out.println(f[v]);
}
}