题解 | #购物单#

#include <algorithm>
#include <array>
#include <iostream>
#include <list>
#include <vector>
using namespace std;
const int N = 32000/10 + 1;
const int M = 60 + 1;
int m, n;
//表示购买1，或者不购买0该物品下的最大满意 w[i][j][k]表示买0件主物品,:j中,有k钱的最大满意
std::array< std::array<std::array<int, N>, M>, 2>  W;
std::array<std::vector<int>,M> step_; //决策步
std::vector<int> step; //更简单的决策步

int main() {
    cin >> n >> m;
    n /= 10;
    std::array<std::array<int, 3>, M>  vpq; //vpq
    int v, p, q;
    //输入
    for (int i = 1; i <= m; i++) {
        cin >> v >> p >> q;
        //cout<<i<<" "<<v<<" "<<p<<" "<<q<<endl;
        vpq[i][0] = v/10;
        vpq[i][1] = p*v;
        vpq[i][2] = q;
        if (q == 0) {
            step_[i].insert(step_[i].begin(),i);
        } else {
            step_[q].push_back(i);
        }
    }
    //决策步
    for (std::vector<int> v:step_){
        if (v.size() && vpq[v.front()][2]!=0){//考虑到没有主
            continue;
        }
        for (int i:v){
            step.push_back(i);
        }
    }
    //动态规划
    for (int i = 0; i < step.size(); i++) { //物品
            int x = step[i];
            int v = vpq[x][0]; //价格
            int w = vpq[x][1]; //满意度
            //找到前一个
            int y = -1;
            bool isman = vpq[x][2]==0;
            for (int j = 0; j <= n; j++) { //cost
                if (i != 0) { //存在前驱
                    y = y = step[i-1];
                    if (j < v) { //买不起

                        W[0][x][j] = std::max(W[0][y][j], W[1][y][j]);
                        W[1][x][j] = -1;
                    } else { //买得起
                        if (isman) { //主
                            //cout<<y<<endl;
                            W[0][x][j] = std::max(W[0][y][j], W[1][y][j]);
                            W[1][x][j] = std::max(W[0][y][j - v], W[1][y][j - v])+w;
                        } else {//附件
                            W[0][x][j] = W[0][y][j];
                            if (W[1][y][j-v]>=0){//合理
                                W[1][x][j] = std::max(W[1][y][j], W[1][y][j - v]+w);
                            }
                            else {
                                 W[1][x][j] = W[1][y][j];
                            }
                        }
                    }
                } else { //没有前驱
                    if (j < v) { //买不起
                        W[0][x][j] = 0;
                        W[1][x][j] = -1;
                    } else { //买得起
                        W[0][x][j] = 0;
                        W[1][x][j] = w;
                    }
                }
                //cout<<x<<" "<<j<<" "<<W[0][x][j]<<" "<<W[1][x][j]<<endl;
            }
        }
        cout<<std::max(W[0][step.back()][n],W[1][step.back()][n])<<endl;
    }
    
// 64 位输出请用 printf("%lld")

0-1背包问题上添加了约束，可以把主物品合配件视为一个整体，每步的选择从{0,1}变成了{{man},{man,1},{man,2},{man,1,2}},共

_{2^t种，t为附件数，总的时间复杂度为m*n*2^t.也可以把附件也视作物品，不过由于物品件的选择存在依赖关系，因此解的结构有变。具体如下：}

_{在G∪{g}中选择的最大满意值 =}

_{1.G的最大满意值}

_{2.G的最大满意值+g的满意值}

_{3.G含g主件的最大满意值+g的满意值}

_{这里忽略了花费，3对应的是g为附件的情况，主件因为不受约束和0-1背包一致，可以和之前一样求出结果，我们在额外求一个选择(0-1中的1)了该主件的最大满意值，选择中增加附件也就可以求解了(从这里可以看到，主件要先求)。我在代码中写的两个表是1.G的含g主件最大满意值，2.G的不含g主件的最大满意值，是差不多的}