链接：https://www.nowcoder.com/questionTerminal/f9c6f980eeec43ef85be20755ddbeaf4?answerType=1&f=discussion
来源：牛客网
王强今天很开心，公司发给N元的年终奖。王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件 附件
电脑 打印机，扫描仪
书柜 图书
书桌 台灯，文具
工作椅 无
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。王强想买的东西很多，为了不超出预算，他把每件物品规定了一个重要度，分为 5 等：用整数 1 ~ 5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是 10 元的整数倍）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
    设第 j 件物品的价格为 v[j] ，重要度为 w[j] ，共选中了 k 件物品，编号依次为 j 1 ， j 2 ，……， j k ，则所求的总和为：
v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] 。（其中 * 为乘号）
    请你帮助王强设计一个满足要求的购物单。

 



输入描述: 

	输入的第 1 行，为两个正整数，用一个空格隔开：N m





	（其中 N （ <32000 ）表示总钱数， m （ <60 ）为希望购买物品的个数。）





	







	从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q





	







	（其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）





	 


输出描述: 

	 输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（ <200000 ）。
示例1

输入 

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

输出 

2200

解题

此题是一个分组背包问题，考虑到一个附件的个数为0个，1个或者2个，和主件的关系能构成5种关系：
  • 不选择主件
  • 只选择主件
  • 选择主件和附件1
  • 选择主件和附件2
  • 选择主件和附件1、附件2
所以将每个主附件组转化成5个单独的商品，该问题即变为01背包问题，但是含有相同主件的多组不能重复选择！！！！！
根据题目条件，假设物品的编号是i，价值为v，重要度是p，是否选择该物品是 X，总的钱数是fmax， 剩余钱数为 f, 当前的最大价值*重要度为V(i, f)能得到以下公式：
约束：
  •     fmax >= v(1)X(1) + v(2)X(2) + ... + v(i)X(i)
  •     if  f < v(i)   V(i, f) = V(i - 1, f)
  •     else if  f>= v(i)  V(i , f) = max(V(i - 1, f), V(i - 1, f - v(i)) + v(i) * p(i))，其中V(i - 1, f)是不放该物品时的价值，V(i - 1, f - v(i)) + v(i) * p(i)是放入该物品时候的价值
以输入来看，此处将主件和附件的物种情况写入
i 1（只选主件）
 2(主件和附件1)
 3（主件和附件2）
 4（主件和附件1、附件2）
 5 6
v 800 1200 1100 1500 400
 500
v*p
 1600 3600 3100 5100 1200 1000

（题目中f的粒度为10元，这里为了简便设置为100元），第1、2、3、4行都是基于第0行生成(不能重复，这四行只要保留最大的数据)
i/f 0 100 200 300 400 500 600 700 800 900 1000
0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1600 1600 1600
2 0 0 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0 0 0
5 0 0 0 0 1200 1200 1200 1200 1600 1600 1600
6 0 0 0 0 1200 1200 1200 1200 1600 2200 2200
所以最高的价值*重要度值为V(6,1000) = 2200元

代码实现： 
#include <bits/stdc++.h>
#define GRANULARITY 10
using namespace std;

class ProdInfo
{
public:
    ProdInfo()
    {
        iPrice = 0;
        iPriority = 0;
        iRelation = 0;
        a1 = 0;
        a2 = 0;
    }
    void setA1(int ID)
    {
        a1 = ID;
    }
    void setA2(int ID)
    {
        a2 = ID;
    }
    friend istream& operator >> (istream& input,ProdInfo& c)
    {
        input >> c.iPrice >> c.iPriority >> c.iRelation;
        return input;
    }
    friend ostream& operator << (ostream& output, ProdInfo & c)
    {
        output << c.iPrice << " " << c.iPriority << " " << c.iRelation << " " << c.a1 << " " << c.a2 << " " << std::endl;
        return output;
    }
public:
    int iPrice;
    int iPriority;
    int iRelation;
    int a1; //第一个附件的id
    int a2; //第二个附件的id
};

int calc(std::vector<struct ProdInfo> & vProdInfo, int iMoney)
{
    std::vector<int> vLine(iMoney / GRANULARITY + 1, 0);
    std::vector<std::vector<int>> vProdMaxValue;
    vProdMaxValue.clear();
    vProdMaxValue.push_back(vLine);
    for(auto itProd = vProdInfo.begin(); itProd != vProdInfo.end(); ++itProd)
    {
        auto vLastLine = vProdMaxValue.at(vProdMaxValue.size() - 1);
        if((*itProd).iRelation != 0)
        {
            continue;
        }
        for(int i = 0; i < vLastLine.size(); ++i)
        {
            if(i * GRANULARITY < (*itProd).iPrice)
            {
                vLine[i] = vLastLine.at(i);
            }
            else
            {
                int iLastValue = vLastLine.at(((i * GRANULARITY - (*itProd).iPrice)) / GRANULARITY);
                int iCurrentValue = (*itProd).iPrice * (*itProd).iPriority;
                vLine[i] = std::max(vLastLine.at(i),
                                    iLastValue + iCurrentValue);
                if((*itProd).a1 != 0 && (*itProd).iPrice + vProdInfo.at((*itProd).a1).iPrice <= i * GRANULARITY)
                {
                    iLastValue = vLastLine.at((i * GRANULARITY - (*itProd).iPrice - vProdInfo.at((*itProd).a1).iPrice) / GRANULARITY);
                    iCurrentValue = (*itProd).iPrice * (*itProd).iPriority + vProdInfo.at((*itProd).a1).iPrice * vProdInfo.at((*itProd).a1).iPriority;
                    vLine[i] = std::max(vLine.at(i),
                                        iLastValue +iCurrentValue);
                }
                if((*itProd).a2 != 0 && (*itProd).iPrice + vProdInfo.at((*itProd).a2).iPrice <= i * GRANULARITY)
                {
                    iLastValue = vLastLine.at((i * GRANULARITY - (*itProd).iPrice - vProdInfo.at((*itProd).a2).iPrice) / GRANULARITY);
                    iCurrentValue = (*itProd).iPrice * (*itProd).iPriority + vProdInfo.at((*itProd).a2).iPrice * vProdInfo.at((*itProd).a2).iPriority;
                    vLine[i] = std::max(vLine.at(i),
                                        iLastValue +iCurrentValue);
                }
                if((*itProd).a1 != 0 && (*itProd).a2 != 0
                        && (*itProd).iPrice + vProdInfo.at((*itProd).a1).iPrice + vProdInfo.at((*itProd).a2).iPrice <= i * GRANULARITY)
                {
                    iLastValue = vLastLine.at((i * GRANULARITY - (*itProd).iPrice - vProdInfo.at((*itProd).a1).iPrice - vProdInfo.at((*itProd).a2).iPrice) / GRANULARITY);
                    iCurrentValue = (*itProd).iPrice * (*itProd).iPriority
                                    + vProdInfo.at((*itProd).a1).iPrice * vProdInfo.at((*itProd).a1).iPriority
                                    + vProdInfo.at((*itProd).a2).iPrice * vProdInfo.at((*itProd).a2).iPriority;
                    vLine[i] = std::max(vLine.at(i),
                                        iLastValue +iCurrentValue);
                }
            }
        }
        vProdMaxValue.push_back(vLine);
    }
    return vProdMaxValue.at(vProdMaxValue.size() - 1).at(vLine.size() - 1);
}

int main()
{
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    int iMoney;
    int iProdNum;
    std::cin >> iMoney >> iProdNum;
    std::vector<struct ProdInfo> vProdInfo;
    for(int iIndex = 0; iIndex < iProdNum; ++iIndex)
    {
        ProdInfo oProdInfo;
        std::cin >> oProdInfo;
        if(oProdInfo.iRelation != 0)
        {
            if(vProdInfo.at(oProdInfo.iRelation - 1).a1 == 0)
            {
                vProdInfo.at(oProdInfo.iRelation - 1).setA1(iIndex);
            }
            else
            {
                vProdInfo.at(oProdInfo.iRelation - 1).setA2(iIndex);
            }
        }
        vProdInfo.push_back(oProdInfo);
    }
    int iMax = calc(vProdInfo, iMoney);
    std::cout << iMax << std::endl;
    return 0;
}