AcWing 3. 完全背包问题
原题链接
简单
作者:
哎嘿_89
,
2023-11-26 12:00:34
,
所有人可见
,
阅读 45
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[] value = new int[1010];
static int[] weigth = new int[1010];
static int[] dp = new int[1010];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
weigth[i] = Integer.parseInt(st.nextToken());
value[i] = Integer.parseInt(st.nextToken());
}
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= v; j++) {
// if (j < weigth[i]) {
// dp[i][j] = dp[i - 1][j];
// } else {
// dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weigth[i]] + value[i]);
// }
// }
// }
for (int i = 1; i <= n; i++) {
for (int j = weigth[i]; j <= v; j++) {
dp[j] = Math.max(dp[j], dp[j - weigth[i]] + value[i]);
}
}
System.out.println(dp[v]);
}
}