题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
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 - 1][j - volumes[i - 1]] + values[i - 1]);
}
}
int res = 0;
for (int j = 1; j <= v; j) res = Math.max(res, dp[n][j]);
System.out.println(dp[n][v]); // 这里同理我们可以写成dp[n][v] 和下面一样dp[n][v] 是到n位置 体积最大为v有最多的价值
// 如果想知道具体这个点最大我们要初始化这个dp[i][j] 为Integer.MIN_VALUE 除了dp[0][0] = 0;
//这是优化版的 */
System.out.println(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 = v; j >= 1; j--) {
if (j >= volumes[i]) count[j] = Math.max(count[j], count[j - volumes[i]] + values[i]);
}
}
//这种初始化 count[i]初始都是0 初始count[i] = 0的意义是volume最大到i 可以有多少价值 假设最大是count[k] k <= v count[v] 也是答案
// 为什么count[k] - count[v] 都是答案尼 我们知道count[volume[x1] + volum[x2] +…] = count[k] = value[x1] + value[x2] + ..= max
// count[m - k] = 0 初始是0 如果count[m - k + volume[x1] + volume[x2] + …] = count[m - k + k] = count[m] = 0 + max= max
// 因为每个初始都是0 所以m 可以从m - k转移过来+ count[k] = max 就是答案
// 如果想要count[i]是正好是价值为i的最大价值 那么就要count[i] = Integer.MIN_VALUE 这样比如最大值count[k]只能从x 转移过来
// 比如最大是count[k] count[0] -> count[volume[x1]] = value[x1] -> count[volume[x1] + volume[x2]] = value[x1] + value[x2]
// ..... count[k] = value[x1] + value[x2] + … 但是如过count[m - k] = IntegerMIN_VALUE 那我们就无法在count[m - k + k]
//上得到最大值 count[m - k + k] = Integer.MIN_VALUE + max 肯定不是最大我们需要遍历一遍count[i]
return count[v];
}
}