#include <iostream> #include <string.h> using namespace std; const int N = 1010; // 定义物品个数和背包体积,以及每个物品的对应的体积和价值,定义成全局可以直接初始化为0 int n, V, v[N], w[N]; // 1. dp[i][j]表示从1~i个物品中选取,背包容量为j的所有选择中,背包所能装的最大价值 // 2. dp[i][j]表示从1~i个物品中选取,背包容量恰好等于j的所有选择中,背包所能装的最大价值 int dp[N][N]; int main() { // 读入数据 cin >> n >> V; for (int i = 1; i <= n; i++) cin >> v[i] >> w[i]; // 1. 解决第一问,背包不需要装满的最大价值 for (int i = 1; i <= n; i++) { for (int j = 1; j <= V; j++) { // dp[i][j]可由两种状态推导而来,选取i物品和不选取i物品 // 1. 背包一定存在不选取i物品的情况,所以可直接把最大价值暂时赋值为dp[i-1][j](从0~(i-1)个物品中选取,背包容量为j的最大价值) dp[i][j] = dp[i - 1][j]; // 2. j-v[i]>=0则表示容量为j可以装下i物品,即存在选取i物品的状态,加上i物品的价值 // 选取i物品后,背包容量j减去i物品体积,再到1~(i-1)的物品中,容量为j-v[i]的情况下找最大 if (j - v[i] >= 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]); } } cout << dp[n][V] << endl; // 2. 解决第二问,背包恰好装满的最大价值 memset(dp, 0, sizeof(dp)); // 清空dp表 for (int j = 1; j <= V; j++) dp[0][j] = -1; // dp表第一行初始化为-1,表示物品为0时,无法恰好装满背包容量j for (int i = 1; i <= n; i++) { for (int j = 1; j <= V; j++) { dp[i][j] = dp[i - 1][j]; // 与第一问一致,但需要在加上一个条件判断dp[i-1][j-v[i]]是否是存在能恰好装满的 if (j - v[i] >= 0 && dp[i - 1][j - v[i]] != -1) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]); } } // dp表最后一个位置有可能是不能够恰好装满容量为V的背包,需特判一下 cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl; return 0; }