//二维未优化
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N]; //v表示该物品的体积,w表示该物品的价值
int f[N][N]; //表示该背包装的东西的总共的价值,其中[][]表示的是当前的状态
int main(){
cin >> n >> m; //输入物品的数量,背包的容积
for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i ++) //因为i = 0的时候是f[0][j],表示的是没有填充物品,所以应该默认都是0,刚好全局变量默认是0
for (int j = 0; j <= m; j ++){
f[i][j] = f[i-1][j];
if (j >= v[i]) f[i][j] = max (f[i][j], f[i-1][j-v[i]] + w[i]);
}
/*
动态规划的问题其实也是一种递归的应用,只不过是用数组将临时的数据进行了储存,使得节约了时间的成本,避免重复计算,
所以一般思考问题如果从正面进行思考就是找最终结果的前一步,再逐渐往前找,得出关系式,
本题是考虑当前的第i件物品是否放入的问题,答案是肯定的,只有放和不放两种情况,不放体现在f[i-1][[j],放体现在f[i][j],
但是不能直接写f[i][j],因为这个值是你要求的,所以要分解问题,考虑到f[i][j]是因为加上了第i个的体积所以写成:
f[i-1][j-v[i]] + w[i],但是要保障下标所以要j >= v[i](可以试着从最小的值开始举例)
*/
cout << f[n][m] << endl;
return 0;
}
//数学递归(把n+1个球转化成n个球的问题,从n+1里面拿m个球相当于是从n个里面拿m个(拿出的那个球不属于应拿出的m个球里的)和从n个里面拿m-1个(拿出的那个球恰好属于应拿出的m个球里的))
//课堂截图
//小晨强推这个网站: https://www.iamshuaidi.com/275.html
//他写的递归也很好理解: https://www.iamshuaidi.com/272.html
🥰