01背包变形

华为机试HJ16购物单这一道题，有年终奖N，需要购买商品，商品有价格v[i]，重要度p[i] ;

  与一般的01背包不同的是，商品还含有附件，每个主件可以有0个、1个或2个附件，购买附件的话就需要购买主件(确实，不然我买这个干嘛呢？)

传统思路

  如果，不考虑附件，那么就是一个传统背包问题，总金额为N，物品价格为v[i]，dp[i][j]表示在下标[0,i]中选取商品得到的最大满意度，满意度=价格*重要度；
那么，就是：
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+v[i]*p[i])
使用滚动数组，改为一维结构：
dp[j]=max(dp[j],dp[j-v[i]]+v[i]*p[i])

添加附件后的转换

  当考虑附件的时候，首先我们需要弄清楚，为了转换为01背包问题商品的个数到底有多少个?
答 ：商品个数==主件个数；对于每一个主件，有几种不同的配置，不同的配置对应不同的价格，随之而来的是不同的满意度

题目说，每一个主件最多有2个附件，所以，我们可以分情况进行讨论：

1. 主件
2. 主件+附件1
3. 主件+附件2
4. 主件+附件1+附件2

对于每一种情况，都有一个满意度，当我们将4种情况看做一个整体的时候，那就和我们传统的背包问题一致了；

for(从少到多遍历物品)
{
   
	for(从大到小遍历背包)
	{
   
		//case1
		dp[]=max(dp[],dp[]);
		//case2
		dp[]=max(dp[],dp[]);
		//case3
		dp[]=max(dp[],dp[]);
		//case4
		dp[]=max(dp[],dp[]);
	}
}

完整代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
   
    int N,m;
    cin>>N>>m;
    
    int price[60][3];
    int value[60][3];
    int dp[32000];
    
    int v,p,q;
    for(int i=1;i<=m;++i)
    {
   
        cin>>v>>p>>q;
        if(0==q)//主件
        {
   
            price[i][0]=v;
            value[i][0]=p*v;
        }
        else if(0==price[q][1])//附件1
        {
   
            price[q][1]=v;
            value[q][1]=p*v;
        }
        else//附件2
        {
   
            price[q][2]=v;
            value[q][2]=p*v;
        }
    }
    
    for(int i=1;i<=m;++i)
    {
   
        for(int j=N/10;j>=price[i][0]/10;--j)
        {
   
            //分4种情况进行讨论：主件，主件+附件1，主件+附件2，主件+附件1+附件2
            //1.主件
            dp[j]=max(dp[j],dp[j-price[i][0]/10]+value[i][0]);
            //2.附件1
            if(price[i][1]!=0)
            {
   
                int total=(price[i][0]+price[i][1])/10;
                if(j>=total)
                {
   
                    dp[j]=max(dp[j],dp[j-total]+value[i][0]+value[i][1]);
                }
            }
            //附件2
            if(price[i][2]!=0)
            {
   
                int total02=(price[i][0]+price[i][2])/10;
                if(j>=total02)
                {
   
                    dp[j]=max(dp[j],dp[j-total02]+value[i][0]+value[i][2]);
                }
                int total012=(price[i][0]+price[i][1]+price[i][2])/10;
                if(j>=total012)
                {
   
                    dp[j]=max(dp[j],dp[j-total012]+value[i][0]+value[i][1]+value[i][2]);
                }
            }
        }
    }
    cout<<dp[N/10]<<endl;  
    return 0;
}

总结

1. 这种类似的问题，根本是将其转换为01背包问题，将附件与主件结合起来作为一个新的商品，或者作为商品的一部分，就像现在手机出好几个配置一样，不同的配置对应不同的价格，随之而来的是不同的满意度；
2. 本题里面，我猜你一定迷惑商品价格price 和价值value里的排列：解答中这样写，我个人认为：
   1. 是为了思路上更加顺畅，比如，q对应的是主件的标号，如果严格对齐使用q-1 在思路上需要一个转变；
   2. 如果严格来写，可以在接收到所有的信息后，使用vector将主件信息(包含附件)push_back进容器，那么后续遍历的时候，就不会出现，商品price==0的情况了