题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
- 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; }