01背包里面就是把集合划分为两大类,选法包含第i个物品,不包含第i个物品。
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
考虑j-w[i]
是否合法
转化为一维。
include[HTML_REMOVED]
using namespace std;
const int MAXN = 1010;
int f[MAXN];
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
int v, w;
cin >> v >> w;
for(int j = m; j >= v; j--)
f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;
}