金明的预算方案

先看题目：https://ac.nowcoder.com/acm/problem/16671
题目描述：
从m个物品中挑选，m个物品中有主件有附件，要求挑选附件的时候必须挑选其所属的主件(每个主件可以有0/1/2个附件)，希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
解题思路：
将主件和其对应的全部附件看成一组，dp[i][j]就是前i组，至多花费j所获得的最大权值。由于一个主件最多有两个附件，每一组的情况无非就是这几个：什么都不选，选主件，选主件和1，选主件和2，选主件和1和2。因此dp[i][j]就是这几种选择中获得权值最大的那个。考虑实现方式，用一个一维数组来记录编号是否为主件，由于并不连续，最好用就地滚动的方式来更新。
代码：

#include<bits/stdc++.h>
using namespace std;
int main_c[70];
int main_w[70];
int attach_c[70][70];
int attach_w[70][70];
int dp[30010];
int main()
{
    int n, m;
    scanf("%d%d",&n,&m);
    memset(main_c, -1, sizeof(main_c));
    for(int i = 1; i <= m; i++) {
        int v, p, q;
        scanf("%d%d%d",&v,&p,&q);
        if(q == 0) {
            main_c[i] = v;
            main_w[i] = p;
        }
        else {
            attach_c[q][0]++;
            attach_c[q][attach_c[q][0]] = v;
            attach_w[q][attach_c[q][0]] = p;
        }
    }
    for(int i = 1; i <= m; i++) {
        if(main_c[i] == -1) continue;
        for(int j = n; j >= main_c[i]; j--) {
            dp[j] = max(dp[j], dp[j-main_c[i]]+main_c[i]*main_w[i]);
            if(j >= (main_c[i]+attach_c[i][1])) {
                dp[j] = max(dp[j], dp[j-main_c[i]-attach_c[i][1]]+main_c[i]*main_w[i]+attach_c[i][1]*attach_w[i][1]);
            }
            if(j >= (main_c[i]+attach_c[i][2])) {
                dp[j] = max(dp[j], dp[j-main_c[i]-attach_c[i][2]]+main_c[i]*main_w[i]+attach_c[i][2]*attach_w[i][2]);
            }
            if(j >= (main_c[i]+attach_c[i][1]+attach_c[i][2])) {
                dp[j] = max(dp[j], dp[j-main_c[i]-attach_c[i][1]-attach_c[i][2]]+main_c[i]*main_w[i]+attach_c[i][1]*attach_w[i][1]+attach_c[i][2]*attach_w[i][2]);
            }
        }
    }
    printf("%d\n",dp[n]);
}