题解 | #购物单#

HJ16 购物单
暴力递归改记忆化搜索

思路：
1.先把附件和组件组合在一起
2.买第一个附件和买第二个附件，以及两个都买的 和两都买不 只买主件的情况

#include<iostream>
#include <set>
#include <queue>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <algorithm>
#include <vector>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <climits>
#include <cstring>
using namespace std;
#define random(a,b) (rand()%(b-a)+a)

unordered_map<string,int> cache;


int process2(vector<Node*> nodes, int index, int m, int N)
{
    string key = to_string(index) + "_" + to_string(N);
    //没钱了
    if(N < 0)
    {
        return -1;
    }
    //买完了，没钱了
    if(m == index  || N == 0)
    {
        return 0;
    }
    if(cache.find(key) != cache.end())
        return cache[key];
    //不买
    int p1 = process2(nodes, index + 1, m, N);

    //买第一个附件
    int p2 = -1;
    if(!nodes[index]->attach.empty())
    {
        int p2next = process2(nodes, index + 1, m, N - nodes[index]->attach[0]->value - nodes[index]->value);
        if(p2next != -1)
        {
            p2 = (nodes[index]->attach[0]->value * nodes[index]->attach[0]->weight) + (nodes[index]->value * nodes[index]->weight) + p2next;
        }
    }
    //买第二个附件
    int p3 = -1;
    int p4 = -1;
    if(nodes[index]->attach.size() == 2)
    {
        int p3next = process2(nodes, index + 1, m, N - nodes[index]->attach[1]->value - nodes[index]->value);
        if(p3next != -1)
        {
            p3 = (nodes[index]->attach[1]->value * nodes[index]->attach[1]->weight) + (nodes[index]->value * nodes[index]->weight) + p3next;
        }
        //两个附件都买
        int p4next = process2(nodes, index + 1, m, N - nodes[index]->attach[0]->value - nodes[index]->attach[1]->value - nodes[index]->value);
        if(p4next != -1)
        {
            p4 = (nodes[index]->attach[0]->value * nodes[index]->attach[0]->weight) + (nodes[index]->attach[1]->value * nodes[index]->attach[1]->weight) + (nodes[index]->value * nodes[index]->weight) + p4next;

        }
    }
    //就买主件
    int p5 = -1;
    int p5next = process2(nodes, index + 1, m, N - nodes[index]->value);
    if(p5next != -1)
    {
        p5 = (nodes[index]->value * nodes[index]->weight) + p5next;
    }
    int a = std::max(p1, p2);
    int b = std::max(a,p3);
    int c = std::max(b,p4);
    int d = std::max(c,p5);
    cache[key] = d;
    return d;
}


int main()
{
    int N,m;
    cin>>N>>m;
    unordered_map<int, Node*> nodes;
    vector<Attach*> attachs;
    int val,weight,num;
    for(int i = 0; i < m; i++){

        cin>>val;
        cin>>weight;
        cin>>num;
        if(num == 0)
        {
            Node * node = new Node(val,weight,num);
            nodes[i] = node;
        }
        else
        {
            Attach * attach = new Attach(val,weight,num);
            attachs.push_back(attach);
        }
    }
    for(int i = 0; i < attachs.size(); i++)
    {
        nodes[attachs[i]->num-1]->attach.push_back(attachs[i]);
    }
    vector<Node*>arr;
    for(auto const &v : nodes)
    {
        arr.push_back(v.second);
    }
    cout<<process2(arr, 0, nodes.size(), N);
    return 0;
}