|
|
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_Knapsack1 {
|
|
|
|
|
|
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;
|
|
|
}
|
|
|
clear();
|
|
|
int ans1 = f1(0, m);
|
|
|
clear();
|
|
|
int ans2 = f2(0, m);
|
|
|
out.println(ans1);
|
|
|
out.println(ans2 == -1 ? 0 : ans2);
|
|
|
out.flush();
|
|
|
}
|
|
|
}
|
|
|
|
|
|
public static void clear() {
|
|
|
for (int i = 0; i < n; i++) {
|
|
|
for (int j = 0; j <= m; j++) {
|
|
|
dp[i][j] = -2;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
public static int f1(int i, int j) {
|
|
|
if (j < 0) {
|
|
|
return -1;
|
|
|
}
|
|
|
if (i == n) {
|
|
|
return 0;
|
|
|
}
|
|
|
if (dp[i][j] != -2) {
|
|
|
return dp[i][j];
|
|
|
}
|
|
|
int p1 = f1(i + 1, j);
|
|
|
int p2 = 0;
|
|
|
int next2 = f1(i + 1, j - v[i]);
|
|
|
if (next2 != -1) {
|
|
|
p2 = w[i] + next2;
|
|
|
}
|
|
|
int ans = Math.max(p1, p2);
|
|
|
dp[i][j] = ans;
|
|
|
return ans;
|
|
|
}
|
|
|
|
|
|
public static int f2(int i, int j) {
|
|
|
if (j < 0) {
|
|
|
return -1;
|
|
|
}
|
|
|
if (i == n) {
|
|
|
return j == 0 ? 0 : -1;
|
|
|
}
|
|
|
if (dp[i][j] != -2) {
|
|
|
return dp[i][j];
|
|
|
}
|
|
|
int p1 = f2(i + 1, j);
|
|
|
int p2 = -1;
|
|
|
int next2 = f2(i + 1, j - v[i]);
|
|
|
if (next2 != -1) {
|
|
|
p2 = w[i] + next2;
|
|
|
}
|
|
|
int ans = Math.max(p1, p2);
|
|
|
dp[i][j] = ans;
|
|
|
return ans;
|
|
|
}
|
|
|
|
|
|
}
|
