题解 | #【模板】01背包#

经典dp问题 整合了几位大佬的代码 记录一下

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int f[N]; // f[j]表示体积为j的情况下的总价值
int v[N], w[N]; // 物品的体积 价值

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    memset(f, -0x3f, sizeof f);  //一开始都初始化为负无穷  方便记录是否有恰好体积为j的情况出现过  
    f[0] = 0; // 最开始体积为0价值为0
    for(int i = 1; i <= n; i ++) 
        for(int j = m; j >= v[i]; j --) // j>=v[i] 保证了可以选择第i个物品
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]); // 这里其实消去了一维
           // 原式为f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
           // 为了防止计算时所需要的上一层的数值被覆盖所以倒序遍历这样算f[j]时用到的f[j - v[i]]就还是和原来一样
        }
    
    int ans1 = 0, ans2 = 0;
    for(int i = 0; i <= m; i ++) ans1 = max(ans1, f[i]); // 找到最大值
    
    if(f[m] < 0) ans2 = 0; // 如果f[m]<0说明没被初始化过 没有体积恰好为m的情况出现
    else ans2 = f[m];  //否则根据定义可知 f[m]的值就是背包恰好装满的情况下的最大值
    
    cout << ans1 << endl;
    cout << ans2 << endl;
}