题解 | #购物单#

• dp问题就是放与不放。对应两种不同的重量以及价值。N个商品的两分支，会对应一个最后的重量序列（解序列）。{..., ..., ...}。
• 序列可以认为是从小到大排列；序列中的每一个值都至少有一个解（至少一个到达路径）。
• 遍历解序列。计算状态1（不放该值已经达到重量w），状态2（放该值后达到重量w，且前状态有解）中，价值最大的一条路径
•     注意，对于正数w，单个商品(5, 2)在正序遍历解序列是，可能存在(5, 2) -> (10, 4)的重复序列。使用逆序遍历。

• 对于附件问题，可以看作dp问题的子问题。可以通过子dp或者遍历的方式实现
• 遍历：（附件数量少时）

    附件不单独考虑，整个作为一个dp考虑。考虑这个主件时，依次考虑主件，主件+附件1，主件+附件2，主件+双附件等四种情况考虑。

<第二次完成时间，51.5min, 6ms - 572kB>

• 子dp：（附件数量>=3时）

    对附件进行dp，f2[i]表示附件重量为i时的价值。i最大值为附件的总价格。

<完成时间，20.5min, 298ms - 528KB>

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, m;   // N为总钱数，m为可购买的物品数
    cin >> N >> m;

    // 下面的m行依次给出价格vi, 重要度pi，是否附件q
    // 由于附件不单独考虑，因此找到包含附件的主件，并计算其附件个数。
    vector<int> p(m + 1), v(m + 1), q(m + 1);
    vector<vector<int>> q_cnt(m+1);
    for(int i = 1; i <= m; i++){
        cin >> p[i] >> v[i] >> q[i];
        q_cnt[q[i]].push_back(i);
    }

    // int f[N + 1];   // f[i]表示当钱数为i时，对应的满意度
    vector<int> f(N + 1, -0x7f7f7f7f);
    f[0] = 0;   // 解序列的初始化。

    // 依次考虑每个商品
    for(int i = 1; i <= m; i++){
        for(int j = N; j >= p[i]; j--){
            // 附件不单独处理
            if(q[i] != 0) continue;


            if(f[j - p[i]] >= 0){
                f[j] = max(f[j], f[j - p[i]] + p[i] * v[i]);    // 若到达当前节点存在两条路径，选择价值最大的一条
            }

            // (1) 采用遍历法处理附件。
            // if(q_cnt[i].size() >= 1){
            //     for(auto k : q_cnt[i]){
            //         if(j >= (p[i] + p[k]) && f[j - p[i] - p[k]] >= 0){
            //             f[j] = max(f[j], f[j - p[i] - p[k]] + p[i] * v[i] + p[k] * v[k]);    
            //         }  
            //     }
            //     if(q_cnt[i].size() == 2){
            //         int k1 = q_cnt[i][0], k2 = q_cnt[i][1];
            //         if(j >= (p[i] + p[k1] + p[k2]) && f[j - p[i] - p[k1] - p[k2]] >= 0){
            //             f[j] = max(f[j], f[j - p[i] - p[k1] - p[k2]] + p[i] * v[i] + p[k1] * v[k1] + p[k2] * v[k2]);   
            //         }  
            //     }
            // }

            // （2）采用子dp法处理附件，找到附件组合对应的结果。针对附件个数>=3的情形。
            /*
                主件必须考虑进来。该主件对应的附件数m_sub，价格重量N_sub。
                遍历次数 m_sub * N_sub。
            f2[i]表示附件中重量为i时，对应的价值。
            */
            int N_sub = 0;
            for(auto k : q_cnt[i]) N_sub += p[k];
            int m_sub = q_cnt[i].size();

            // int f2[N_sub + 1];
            vector<int> f2(N_sub + 1, -0x7f7f7f7f);     
            f2[0] = 0;

            // 找到N个附件的解序列
            for(int k = 0; k < m_sub; k++){
                int cur = q_cnt[i][k];
                for( int l = N_sub; l >= p[cur]; l--){
                    if(f2[l - p[cur]] >= 0){
                        f2[l] = max(f2[l], f2[l - p[cur]] + p[cur] * v[cur]);
                    }
                }
            }

            // 将附件的各种解序列，同步到主序列中
            for(int w = 1; w <= N_sub; w++){
                // f2[i]为附件重量i时，对应的价值
                if(f2[w] > 0){
                    if(j >= (p[i] + w) && f[j - p[i] - w] >= 0){
                        f[j] = max(f[j], f[j - p[i] - w] + p[i] * v[i] + f2[w]);
                    }
                }
            }

        }
    }

    int ans = 0;
    for(int i = 1; i <= N; i++){ 
        if(f[i] > ans){
            ans = f[i];
        }  
    }

    cout << ans;
}