2.9

金明的预算方案

这是一道需要转化的分组背包问题。如在每组中只能取1个，只需用dp[i][j]表示前i组中w不超过j的最优解，每次在每组中选取最优解即可

用物品组的思想考虑题中极其特殊的依赖关系：物品不能既作主件又作附件，每个主件最多有两个附件，可以发现一个主件和它的两个附件等价于一个由四个物品组成的物品组，从而用分组背包问题求解。（Note:发现问题中数据间关系的特殊性）

小技巧：发现数据均为10的倍数时，影响到先将所有数除以10，最后再乘10，从而时间复杂度和空间复杂度均缩小10倍！（发现问题特点）

初始化时寻找最简便的模式

当vector.size()在循环中会改变时,循环条件的终止一定不能写size(),要在循环前先取出！

附上代码

#include <bits/stdc++.h>
using namespace std;
struct solu
{
    int w,v;
    solu(int nw, int nv){w=nw;v=nv;} //构造函数 
};
vector<solu> a[65];
int n,m,dp[32005];
map<int,int> mp;
int main()
{
    cin >> n >> m;n/=10;  //小技巧，时间复杂度和空间复杂度缩小10倍！ 
    int k=0;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin >> x >> y >> z;x/=10;
        if(z==0)  //分类处理 
        {
            k++;
            a[k].push_back(solu(x,x*y));
            mp[i]=k;
        }
        else
        {
            int len=a[mp[z]].size();  //这里一定要先把size取出来，在添加过程中size会不断增加!!! 
            for(int j=0;j<len;j++) a[mp[z]].push_back(solu(x+a[mp[z]][j].w,x*y+a[mp[z]][j].v)); //较简便的初始化模式
        }
    }
    for(int i=1;i<=k;i++)  //分组背包 
    {
        for(int j=n;j>=0;j--)
        {
            for(int q=0;q<a[i].size();q++)
            {
                if(j>=a[i][q].w) dp[j]=max(dp[j],dp[j-a[i][q].w]+a[i][q].v); //选取每组的最优解 
            }
        }
    }
    cout << dp[n]*10; //结果一定要记得乘10 
    return 0;
}