01背包变式

01背包的变式题

思路：对于经典的01背包本题的不同之处在于多了只有当主件购买时才可以购买附件，
并且每个主件最多只有2个附件。思考一下不难发现，将原本的01背包的决策（选或不选）
变为现在的决策（不选主件|选主件|选主件+附件1|选主件+附件2|选主件+附件1+附件2）。
dp[i][j]表示在前i件物品当金钱为j时的最大价值，如果第i件物品为附件则dp[i][j]=dp[i-1][j](略过
该判断附件的情况在主件时一并判断了)。
接下来是判断针对dp[i][j]判断5个决策。

int c[Max],v[Max],f[Max];//分别存储价格、重要程度、所对应主件
vector<int> vec[Max];//存储主件对应的附件</int>

dp[i][j] = dp[i - 1][j];
if (f[i] != 0) continue;
if (j >= c[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + v[i] * c[i]); //决策：选择要主件和不要主件
for (int k = 0; k < vec[i].size(); k++)
{
if (j >= c[i] + c[vec[i][k]]) dp[i][j] = max(dp[i][j], dp[i - 1][j - c[i] - c[vec[i][k]]] + v[i] * c[i] + v[vec[i][k]] * c[vec[i][k]]);
} //决策：根据附件的的多少选择要主键+一个附件
if (vec[i].size() == 2 && j >= c[i] + c[vec[i][0]] + c[vec[i][1]])
{
dp[i][j] = max(dp[i][j], dp[i - 1][j - c[i] - c[vec[i][0]] - c[vec[i][1]]] + c[i] * v[i] + c[vec[i][1]] * v[vec[i][1]] + c[vec[i][0]] * v[vec[i][0]]);
} //决策：如果有两个附件则判断两个附件+主件一起购买的情况

当然可以有滚动数组优化为一维，看数据不大就直接开2维了。

AC代码

#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<algorithm>
#include<set>
#include<cmath>
#include<iomanip>
#include<memory.h>
#include<queue>
#define pii pair<int,int>
using namespace std;
typedef long long ll;
const int Max = 1e5 + 5;
int lst[Max];
int dp[65][Max];
int c[Max],v[Max],f[Max];
vector<int> vec[Max];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &c[i], &v[i], &f[i]);
        vec[f[i]].push_back(i);
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (f[i] != 0) continue;
            if (j >= c[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + v[i] * c[i]);
            for (int k = 0; k < vec[i].size(); k++)
            {
                if (j >= c[i] + c[vec[i][k]]) dp[i][j] = max(dp[i][j], dp[i - 1][j - c[i] - c[vec[i][k]]] + v[i] * c[i] + v[vec[i][k]] * c[vec[i][k]]);
            }
            if (vec[i].size() == 2 && j >= c[i] + c[vec[i][0]] + c[vec[i][1]])
            {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - c[i] - c[vec[i][0]] - c[vec[i][1]]] + c[i] * v[i] + c[vec[i][1]] * v[vec[i][1]] + c[vec[i][0]] * v[vec[i][0]]);
            }
        }
    }
    cout << dp[m][n] << endl;
}