P1064 [NOIP2006 提高组] 金明的预算方案

$01$背包的变式，有依赖的背包题
题目链接

思路

考虑到我们一般的$01$背包题，动态转移方程成立条件为：若背包容量能容纳该物品，则判断取最大，否则跳过
而该题有多种状态，对于每一种物品（主物品＋配套的附物品）
不取主物品
取主物品不取附属物品
取主物品和附属物品$1$，不取附属物品$2$（如果有的话）
取主物品和附属物品$2$，不取附属物品$1$（如果有的话）
取主物品和附属物品$1,2$（如果有的话）
然后打上$01$背包的板子就行了

ACcode

#include<bits/stdc++.h>

using namespace std;

const int M = 3e5 + 9;
int dp[M];
int cv[M], cw[M];
int fv[M][7], fw[M][7];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;cin >> n >> m;
    int a, b, c;
    for (int i = 1;i <= m;i++) {
        cin >> a >> b >> c;
        if (!c) {
            cv[i] = a;
            cw[i] = a * b;
        }
        else {
            fv[c][0]++;
            fv[c][fv[c][0]] = a;
            fw[c][fv[c][0]] = b * a;
        }
    }
    for (int i = 1;i <= m;i++) {
        for (int j = n;j >= cv[i];j--) {
            dp[j] = max(dp[j], dp[j - cv[i]] + cw[i]);
            if (j >= cv[i] + fv[i][1])dp[j] = max(dp[j], dp[j - cv[i] - fv[i][1]] + cw[i] + fw[i][1]);
            if (j >= cv[i] + fv[i][2])dp[j] = max(dp[j], dp[j - cv[i] - fv[i][2]] + cw[i] + fw[i][2]);
            if (j >= cv[i] + fv[i][1] + fv[i][2])dp[j] = max(dp[j], dp[j - fv[i][1] - cv[i] - fv[i][2]] + cw[i] + fw[i][1] + fw[i][2]);
        }
    }
    cout << dp[n];
    return 0;
}