HJ16 购物单

https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4?tpId=37&rp=1&ru=%2Fexam%2Foj%2Fta&qru=%2Fexam%2Foj%2Fta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37&difficulty=&judgeStatus=&tags=&title=&gioEnter=menu

王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件 附件
电脑 打印机，扫描仪
书柜 图书
书桌 台灯，文具
工作椅 无
如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。
每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。
王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。他希望在花费不超过 N 元的前提下，使自己的满意度达到最大。
满意度是指所购买的每件物品的价格与重要度的乘积的总和，假设设第ii件物品的价格为v[i]v[i]，重要度为w[i]w[i]，共选中了kk件物品，编号依次为j1,j2,...,jkj1​,j2​,...,jk​，则满意度为：v[j1]∗w[j1]+v[j2]∗w[j2]+…+v[jk]∗w[jk]v[j1​]∗w[j1​]+v[j2​]∗w[j2​]+…+v[jk​]∗w[jk​]。（其中 * 为乘号）
请你帮助王强计算可获得的最大的满意度。

思路

我们可以这样理解，对于同一个物品，现在它的价格、重要度都是可变的
那么我们只需要对每一个主件尝试如下四种情况：

仅加入一个主件；
加入主件和第一个附件；
加入主件和第二个附件；
加入主件和两个附件；

在以上四种情况中找到最大值就能回归到0-1背包问题。

所以我们先考虑一下普通的0-1背包问题

对于一个可承重C的背包，我们假设所有物品的重量数据保存在w[]，所有价值数据保存在v[]。那么我们有以下的推导式：
dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[j]]+v[j])dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[j]] + v[j])dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[j]]+v[j])

那么对于“购物单”这道题，我们可以有如下抽象：
dp[i][j]=max(dp[i−1][j], {四种情况产生的价值})dp[i][j] = max(dp[i-1][j],\ {四种情况产生的价值})dp[i][j]=max(dp[i−1][j], {四种情况产生的价值})

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
	int N, m; // N 奖金 m 物品个数
    cin >> N >> m;
    N /= 10; // 由于所有的价格都是10的整倍数，所以可以均除10以简化运算复杂度

    int price, priority, hasAttachments;
    vector<vector<int>> data(m+1, vector<int>(6, 0));

    for(int i = 1; i <= m; i++){
        cin >> price >> priority >> hasAttachments;
        if(hasAttachments == 0){
            data[i][0] = price/10;
            data[i][1] = priority;
            // count++;
        }
        else if(data[hasAttachments][2] == 0){
            data[hasAttachments][2] = price/10;
            data[hasAttachments][3] = priority;
        }
        else {
            data[hasAttachments][4] = price/10;
            data[hasAttachments][5] = priority;
        }
    }

	vector<int> dp(N+1, 0);
    for(int i = 1; i < m+1; i++){
        for(int j = N; j >= 1; j--){
            int pricePrime = data[i][0];
            int priceAtta1 = data[i][2];
            int priceAtta2 = data[i][4];
            
            int priorPrime = data[i][1];
            int priorAtta1 = data[i][3];
            int priorAtta2 = data[i][5];

            dp[j] = j >= pricePrime ? max(dp[j - pricePrime]
                                            + priorPrime * pricePrime, 
                                            dp[j]) : dp[j];
            dp[j] = j >= (pricePrime + priceAtta1) ? max(dp[j - pricePrime - priceAtta1]
                                                        + priorPrime * pricePrime 
                                                        + priorAtta1 * priceAtta1, 
                                                        dp[j]) : dp[j];
            dp[j] = j >= (pricePrime + priceAtta2) ? max(dp[j - pricePrime - priceAtta2]
                                                        + priorPrime * pricePrime 
                                                        + priorAtta2 * priceAtta2, 
                                                        dp[j]) : dp[j];
            dp[j] = j >= (pricePrime + priceAtta1 + priceAtta2) ? 
                                                        max(dp[j - pricePrime - priceAtta1 - priceAtta2]
                                                        + priorPrime * pricePrime 
                                                        + priorAtta1 * priceAtta1
                                                        + priorAtta2 * priceAtta2, 
                                                        dp[j]) : dp[j];
        }
    }
    cout << dp[N] * 10 <<endl;
    return 0;
}