HJ16 购物单 题解

by 限时烟花

1. 抽丝剥茧

看到题目的第一想法就是很像背包问题，如果不考虑“附件”的问题，那么就是0-1背包问题。
一开始觉得要考虑附件好像整个问题就会变得复杂，还挺头痛的。
但是所谓附件，表面上在制造问题，但是实际上也真的就是“附件”。

2. 化繁为简

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

1. 仅加入一个主件；
2. 加入主件和第一个附件；
3. 加入主件和第二个附件；
4. 加入主件和两个附件；

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

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

对于一个可承重C的背包，我们假设所有物品的重量数据保存在w[]，所有价值数据保存在v[]。那么我们有以下的推导式：

那么对于“购物单”这道题，我们可以有如下抽象：

3. 码上行动

#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;
    // 使用一个(m+1)X6的数组存储数据，m+1是根据物品编号，0作废；6考虑可能有附件的最多的情况
    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;
        }
        // 第一个附件
        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<vector<int>> dp(m+1, vector<int>(N+1, 0));
    for(int i = 1; i < m+1; i++){
        for(int j = 1; j < N+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[i][j] = j >= pricePrime ? max(dp[i-1][j - pricePrime] 
                                            + priorPrime * pricePrime, 
                                            dp[i-1][j]) : dp[i-1][j];
            dp[i][j] = j >= (pricePrime + priceAtta1) ? max(dp[i-1][j - pricePrime - priceAtta1]
                                                        + priorPrime * pricePrime 
                                                        + priorAtta1 * priceAtta1, 
                                                        dp[i][j]) : dp[i][j];
            dp[i][j] = j >= (pricePrime + priceAtta2) ? max(dp[i-1][j - pricePrime - priceAtta2]
                                                        + priorPrime * pricePrime 
                                                        + priorAtta2 * priceAtta2, 
                                                        dp[i][j]) : dp[i][j];
            dp[i][j] = j >= (pricePrime + priceAtta1 + priceAtta2) ? 
                                                        max(dp[i-1][j - pricePrime - priceAtta1 - priceAtta2]
                                                        + priorPrime * pricePrime 
                                                        + priorAtta1 * priceAtta1
                                                        + priorAtta2 * priceAtta2, 
                                                        dp[i][j]) : dp[i][j];
        }
    }
    cout << dp[m][N] * 10 <<endl;
    return 0;
}

dp数组更新的可视化过程如下：

4. 心有成算

1. 空间复杂度：dp数组的空间大小为mN，数据vector的大小是(m+1)$\times \backslash times$6，故空间复杂度为$O(mN)O(mN)$;
2. 时间复杂度：因为是对dp数组的所有元素进行一边遍历，故空间复杂度为$O(mN)O(mN)$。

5. 精益求精

解法一中比较大的问题是空间复杂度，使用的dp数组的大小是$(m+1)\times (N+1)(m+1)\; \backslash times\; (N+1)$，这使得空间复杂度非常大。同时根据解法我们可以看到，对于任意的$dp[i][j]dp[i][j]$它只与$dp[i-1][]dp[i-1][\backslash \; \backslash \; ]$（即第$i-1i-1$行）有关。所以我们可以考虑对dp数组的大小进行优化。 使用单行的dp数组来保存上一行的dp状态，并且大小可以以输入的N为基准。

改进过后的代码如下：

#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;
}

复杂度分析

1. 时间复杂度：没有改变，仍为$O(mN)O(mN)$;
2. 空间复杂度：$O(N)O(N)$。