洛谷 金明的预算（依赖背包）

 

 

此题第一次遇到没什么思路，现在已经知道是依赖型背包。

对于每个主件，根据组合，如果有n个附件，则搭配附件的话最多可以有(n + 1) * n / 2 种组合（总组合数还要 + 1 主件本身），用每种组合更新当前dp[j]（前提：当j >= 当前组合所需要钱数），感觉依赖型背包n不会太大，不然讨论的组合数太多。

对于本题，v需要计算处理得到（v实际 = v * p， 思维点），然后视为普通的01背包递推即可。

还有一个地方用法精炼，annex_w[i][0]记录附件个数，annex_w[i][1], annex_w[i][2]记录相应附件的值。（虽然也可以另开一个一维数组记录每个主件的附件个数）

终于找到了bug，题目的编号没理解对，放上正确和错误代码对比。

正确代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 65;
const int maxsz = 6e5 + 10;
int main_w[maxn], main_v[maxn];
int annex_w[maxn][3], annex_v[maxn][3];
int dp[maxsz];
int N, m;
int cnt;

int main()
{
    cin >> N >> m;
    //cnt = 1;
    int v, p, q;
    for(int i = 1; i <= m; i++)        //按照顺序依次读入即可
    {
        cin >> v >> p >> q;
        if(q == 0)
        {
            main_w[i] = v;
            main_v[i] = v * p;
            //main_w[cnt] = v;
            //main_v[cnt] = v * p;
            //cnt++;
        }
        else
        {
            annex_w[q][0]++;
            annex_w[q][annex_w[q][0]] = v;
            annex_v[q][annex_w[q][0]] = v * p;
        }
    }

    for(int i = 1; i <= m; i++)            //i < cnt错误
    {
        if(main_w[i] == 0)  continue;        
        for(int j = N; j >= main_w[i]; j--)    //当前i没有主件直接跳过
        {
            dp[j] = max(dp[j], dp[j - main_w[i]] + main_v[i]);

            if(annex_w[i][0] >= 1 && j >= main_w[i] + annex_w[i][1])
            {
                dp[j] = max(dp[j], dp[j - main_w[i] - annex_w[i][1]] + main_v[i] + annex_v[i][1]);
            }
            if(annex_w[i][0] >= 2 && j >= main_w[i] + annex_w[i][2])
            {
                dp[j] = max(dp[j], dp[j - main_w[i] - annex_w[i][2]] + main_v[i] + annex_v[i][2]);

            }
            if(annex_w[i][0] >= 2 && j >= main_w[i] + annex_w[i][1] + annex_w[i][2])
            {
                dp[j] = max(dp[j], dp[j - main_w[i] - annex_w[i][1] - annex_w[i][2]] + main_v[i] + annex_v[i][1] + annex_v[i][2]);
            }
        }
    }
    cout << dp[N] << endl;
   
    return 0;
}

错误代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 65;
const int maxsz = 6e5 + 10;
int main_w[maxn], main_v[maxn];
int annex_w[maxn][3], annex_v[maxn][3];
int dp[maxsz];
int N, m;
int cnt;

int main()
{
    cin >> N >> m;
    cnt = 1;
    int v, p, q;
    for(int i = 0; i < m; i++)
    {
        cin >> v >> p >> q;
        if(q == 0)
        {
            main_w[cnt] = v;
            main_v[cnt] = v * p;
            cnt++;                        //仔细读题，不能用cnt计数，编号不对应。
        }
        else
        {
            annex_w[q][0]++;
            annex_w[q][annex_w[q][0]] = v;
            annex_v[q][annex_w[q][0]] = v * p;
        }
    }

    for(int i = 1; i < cnt; i++)
    {
        for(int j = N; j >= main_w[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - main_w[i]] + main_v[i]);

            if(annex_w[i][0] >= 1 && j >= main_w[i] + annex_w[i][1])
            {
                dp[j] = max(dp[j], dp[j - main_w[i] - annex_w[i][1]] + main_v[i] + annex_v[i][1]);
            }
            if(annex_w[i][0] >= 2 && j >= main_w[i] + annex_w[i][2])
            {
                dp[j] = max(dp[j], dp[j - main_w[i] - annex_w[i][2]] + main_v[i] + annex_v[i][2]);

            }
            if(annex_w[i][0] >= 2 && j >= main_w[i] + annex_w[i][1] + annex_w[i][2])
            {
                dp[j] = max(dp[j], dp[j - main_w[i] - annex_w[i][1] - annex_w[i][2]] + main_v[i] + annex_v[i][1] + annex_v[i][2]);
            }
        }
    }
    cout << dp[N] << endl;
    return 0;
}