题目描述
blablabla
JAVA 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
public class Main {
/**
* 优秀文章
* https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html#%E4%B8%80%E7%BB%B4dp%E6%95%B0%E7%BB%84-%E6%BB%9A%E5%8A%A8%E6%95%B0%E7%BB%84
*/
/**
* 二维下的状态定义f[i][j]是前 i件物品,背包容量 j下的最大价值。
* 一维下,少了前 i件物品这个维度,我们的代码中决策到第 i件物品(循环到第i轮),
* f[j]就是前i轮已经决策的物品且背包容量 j下的最大价值。
*/
/**
* 如果使用顺序,会先更新f[4],再更新f[7],对于这个书包问题来讲,
* 就是有可能,在更新f[4]的时候,已经把这次能加的物品加进来了,
* 然后更新f[7]的时候,还有可能再加一次,所以必须使用逆序,
* 保证,f[4]是没有加入新物品前,背包里的最优解。
*/
static int N = 1010;
static int[] p = new int[N];//p[j]定义:N件物品,背包容量j下的最优解。 //有N件物品,则需要N次决策,
static int[] v = new int[N];
static int[] w = new int[N];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s[] = br.readLine().split(" ");
int n = Integer.parseInt(s[0]);//物品数量
int V = Integer.parseInt(s[1]);//背包容积
for (int i = 1; i <= n; i++) {
String ss[] = br.readLine().split(" ");
v[i] = Integer.parseInt(ss[0]);
w[i] = Integer.parseInt(ss[1]);
}
for (int i = 1; i <= n; i++) {
for (int j = V; j >= v[i]; j--) {
//p[i][j] = p[i-1][j];
// 优化前,不选
//p[j] = p[j]; //自动成立
// if(j >= v[i])
// {
// //p[i][j] = Math.max(p[i][j],p[i-1][j-v[i]] + w[i]);优化前 //选
// }
p[j] = Math.max(p[j],p[j-v[i]]+w[i]);
/**
* dp[j]有两个选择,一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j],即不放物品 i
* 一个是取dp[j - weight[i]] + value[i],即放物品i,指定是取最大的,毕竟是求最大价值,
* dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
*/
}
}
System.out.println(p[V]);
}
}