#define MAXN 1005
int n; // 物品数
int v; // 背包容量
int c[MAXN]; // 物品费用
int w[MAXN]; // 物品价值
int f[MAXN][MAXN]; // f[i][j],j体积下前i个物品的最大价值
int knapsack01() {
cin >> n >> v;
for(int i = 1; i <= n; i++) { // 下标从1开始
cin >> c[i] >> w[i];
}
// 注意这里隐含设置了取0件物品和背包容量为0时f数组对应的值全为0的情况
// for(int i = 0; i <= v; i++) f[0][i] = 0;
// for(int i = 0; i <= n; i++) f[i][0] = 0;
for(int i = 1; i <= n; i++) { // n个物品,对每个物品决策一次
for(int j = 1; j <= v; j++) { // 枚举背包的容量,计算当前物品在该容量下的价值
if(j < c[i]) {
// 当前背包容量j装不下第i个物品,则价值等于前i-1个物品
f[i][j] = f[i-1][j];
} else {
// 能装,按方程进行决策
// 注意,这里其实只需要在j == c[i]时计算一次,表示恰好能装下时的情况
// 当j > c[i]时,表示背包容量有冗余,f[i][j]可直接设置成f[i][j-1]或f[i][c[i]]
f[i][j] = max(f[i-1][j], f[i-1][j - c[i]] + w[i]);
}
}
}
return f[n][v];
}