题解 | 【模板】完全背包

#牛客春招刷题训练营# + 链接

第一个问题是完全背包问题的经典模板

1) dpi,j = dpi-1,j , dpi-1,j-v +w, dpi-1,j-2v + 2w ...

2) dpi,j-v = dpi-1,j-v, dpi-1,j-2v + w ...

当计算1时候，2已经在顺序枚举的过程中算出了，所以可以用2式替代1式，就不用再枚举k了

第二个问题

恰好装满，只需要再枚举的过程中判断前一个状态是否合法即是否前一个状态初始是0，是0则非法（除了f[0][0]）

#include <bits/stdc++.h>
#define v first
#define w second
using namespace std;
//dpi,j = dpi-1,j , dpi-1,j-v +w, dpi-1,j-2v + 2w ...
//dpi,j-v =         dpi-1,j-v,    dpi-1,j-2v + w ...
//dpi j = max dpi-1, j , dpi,j-v + w
const int N = 1e3 + 10;
int dp[N][N];
bool f[N][N];
int mx = 0;
pair<int, int> a[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i ++) {
        cin >> a[i].v >> a[i].w;
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1 ; i <= n ; i ++) {
        for (int j = 1 ; j <= m ; j ++) {
            dp[i][j] = dp[i - 1][j];
            if (j - a[i].v >= 0)dp[i][j] = max(dp[i][j], dp[i][j - a[i].v] + a[i].w);
        }
    }
    f[0][0] = true;
    cout << dp[n][m] << '\n';
    memset(dp, 0, sizeof dp);
    for (int i = 1 ; i <= n ; i ++) {
        for (int j = 0 ; j <= m ; j ++) {
            if (f[i - 1][j]) {
                f[i][j] = true;
                dp[i][j] = dp[i - 1][j];
            }
            if (j - a[i].v >= 0 && f[i][j - a[i].v]) {
                f[i][j] = true;
                dp[i][j] = max(dp[i][j], dp[i][j - a[i].v] + a[i].w);
            }
        }
    }
    cout << dp[n][m] << '\n';
}
// 64 位输出请用 printf("%lld")