|
|
package 第03期.mca_09;
|
|
|
|
|
|
// 背包问题
|
|
|
// 测试链接 : https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e
|
|
|
// 请同学们务必参考如下代码中关于输入、输出的处理
|
|
|
// 这是输入输出处理效率很高的写法
|
|
|
// 提交以下所有代码，把主类名改成Main，可以直接通过
|
|
|
import java.io.BufferedReader;
|
|
|
import java.io.IOException;
|
|
|
import java.io.InputStreamReader;
|
|
|
import java.io.OutputStreamWriter;
|
|
|
import java.io.PrintWriter;
|
|
|
import java.io.StreamTokenizer;
|
|
|
|
|
|
public class Code04_Knapsack2 {
|
|
|
|
|
|
public static int MAXN = 1010;
|
|
|
public static int[] v = new int[MAXN];
|
|
|
public static int[] w = new int[MAXN];
|
|
|
public static int[][] dp = new int[MAXN][MAXN];
|
|
|
public static int n, m;
|
|
|
|
|
|
public static void main(String[] args) throws IOException {
|
|
|
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
|
|
|
StreamTokenizer in = new StreamTokenizer(br);
|
|
|
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
|
|
|
while (in.nextToken() != StreamTokenizer.TT_EOF) {
|
|
|
n = (int) in.nval;
|
|
|
in.nextToken();
|
|
|
m = (int) in.nval;
|
|
|
for (int i = 0; i < n; i++) {
|
|
|
in.nextToken();
|
|
|
v[i] = (int) in.nval;
|
|
|
in.nextToken();
|
|
|
w[i] = (int) in.nval;
|
|
|
}
|
|
|
int ans1 = f1();
|
|
|
int ans2 = f2();
|
|
|
out.println(ans1);
|
|
|
out.println(ans2 == -1 ? 0 : ans2);
|
|
|
out.flush();
|
|
|
}
|
|
|
}
|
|
|
|
|
|
public static int f1() {
|
|
|
for (int j = 0; j <= m; j++) {
|
|
|
dp[n][j] = 0;
|
|
|
}
|
|
|
for (int i = n - 1; i >= 0; i--) {
|
|
|
for (int j = 0; j <= m; j++) {
|
|
|
dp[i][j] = dp[i + 1][j];
|
|
|
if (j - v[i] >= 0) {
|
|
|
dp[i][j] = Math.max(dp[i][j], w[i] + dp[i + 1][j - v[i]]);
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
return dp[0][m];
|
|
|
}
|
|
|
|
|
|
public static int f2() {
|
|
|
dp[n][0] = 0;
|
|
|
for (int j = 1; j <= m; j++) {
|
|
|
dp[n][j] = -1;
|
|
|
}
|
|
|
for (int i = n - 1; i >= 0; i--) {
|
|
|
for (int j = 0; j <= m; j++) {
|
|
|
dp[i][j] = dp[i + 1][j];
|
|
|
if (j - v[i] >= 0 && dp[i + 1][j - v[i]] != -1) {
|
|
|
dp[i][j] = Math.max(dp[i][j], w[i] + dp[i + 1][j - v[i]]);
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
return dp[0][m];
|
|
|
}
|
|
|
|
|
|
}
|
