题目描述
blablabla
样例
blablabla
import java.util.Scanner;
class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), v = sc.nextInt();
int[] volumes = new int[n], values = new int[n];
for (int i = 0; i < n; i) {
volumes[i] = sc.nextInt();
values[i] = sc.nextInt();
}
int[][] dp = new int[n + 1][v + 1]; // 这种初始化也是
for (int i = 1; i <= n; i) {
for(int j = 1; j <= v; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= volumes[i - 1]) dp[i][j] = Math.max(dp[i][j], dp[i][j - volumes[i - 1]] + values[i - 1]);
// 完全背包 和0 1背包的区别是
// 0 1 // 0 1是 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - volumes[i - 1]] + values[i - 1]);这个不选 和选了从上行转移下来+ 当前价值
//完全 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - volumes[i - 1]] + values[i - 1]) // 这个选了+ 从相同行转移过来 + 当前价值
// 仔细想想就是打表的时候0 - 1背包 假设row i = 1 0 1背包每个数字只能减去values[i]得到
//而且是从dp[i - 1][j - volumes] 也就是row = 0 转移过来 所有j >= volumes[i]时候
//dp[i][j] 都是从上一行dp[i - 1][j - volumes] 转移过来都是values[i] 而且最大就是values[i] 不会更大了
// 完全背包可以有多个 积累不停的加上values[i] 而且可以是从dp[i - 1][j] 和dp[i][j - volumes[i]] 可以从相同行转移过来
// 当前行最大取决背包多大
}
}
//System.out.print(dp[n][v]);
System.out.print(find(n, v, volumes, values));
}
public static int find(int n, int v, int[] volumes, int[] values) {
int[] count = new int[v + 1];
for (int i = 0; i < n; i++) {
for (int j = 1; j <= v; j++) { // 这里和0 1背包有很大的不同 0 1是for (int j = v; j >= 1; j--)
// 为什么 0 1那样写 因为0 1是从上一行转移过来 count[j] = Mtah.max(count[j], count[j - volumes[i]] + values[i])
// 从上一行count[j - volumes[i]] 转移过来 必须保证没改变先 所以先从大的开始算 如果从小的count[j - volumes[i]]可能有改动了
// 完全背包因为 从这行开始 所以从左到右
if (j >= volumes[i]) count[j] = Math.max(count[j], count[j - volumes[i]] + values[i]);
}
}
return count[v];
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla