算法题-购物单

购物单

https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4?tpId=37&tqId=21239&tPage=1&rp=&ru=%2Fta%2Fhuawei&qru=%2Fta%2Fhuawei%2Fquestion-ranking

链接：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

输入

输出

解题

此题是一个分组背包问题，考虑到一个附件的个数为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	100	200	300	400	500	600	700	800	900	1000
0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	1600	1600	1600
2	0	0	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0	0	0
4	0	0	0	0	0	0	0	0	0	0
5	0	0	0	1200	1200	1200	1200	1600	1600	1600
6	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;
}