#include <stdio.h>
#define MAX_N 100
#define MAX_W 100
int weight[MAX_N], value[MAX_N];
int dp[MAX_N + 1][MAX_W + 1];
int knapsack(int n, int w) {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= w; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (weight[i - 1] <= j) {
dp[i][j] = dp[i - 1][j] > (dp[i - 1][j - weight[i - 1]] + value[i - 1]) ? dp[i - 1][j] : (dp[i - 1][j - weight[i - 1]] + value[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][w];
}
int main() {
int n;
int w;
printf("请输入物品数量和背包容量:");
scanf("%d %d", &n, &w);
printf("请分别输入每个物品的重量和价值:\n");
for (int i = 0; i < n; i++) {
scanf("%d %d", &weight[i], &value[i]);
}
printf("背包所能装下的最大价值为:%d\n", knapsack(n, w));
return 0;
}