Shopping list--

Shopping list

subject

：
describe
Wang Qiang is very happy today , The company issued N A year-end bonus of yuan . Wang Qiang decided to use the year-end bonus for shopping , He divided the items he wanted to buy into two categories ： Main parts and accessories , The attachment is subordinate to a main component , Here are some examples of main components and accessories ：

Main parts The attachment
The computer The printer , Scanner
Bookcase The book
desk Desk lamp , Stationery
Work chair nothing

If you want to buy items classified as accessories , You must buy the main part of the accessory first , And each item can only be purchased once . Each main component can have 0 individual 、 1 Or 2 Attachments . Attachments no longer have their own attachments . Wang Qiang wants to buy a lot of things , In order not to exceed the budget , He set an importance level for each item , It is divided into 5 etc. ： Integers 1 ~ 5 Express , The first 5 And so on . He also looked up the price of each item on the Internet （ All are 10 An integral multiple of one yuan ）. He hopes not to exceed N element （ Can be equal to N element ） Under the premise of , To maximize the sum of the product of the price of each item and its importance .
Set the first j The price of the item is v[j] , The importance is w[j] , A total of k Item , The serial numbers are j 1 , j 2 ,……, j k , Then the sum of the requirements is ：
v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] .（ among * For the multiplier ）
Please help Wang Qiang design a shopping list that meets the requirements .

Input description ：
Input the 1 That's ok , For two positive integers , Separated by a space ：N m

（ among N （ <32000 ） It means the total amount of money , m （ <60 ） For the number of items you want to buy .）

From 2 Go to the first place m+1 That's ok , The first j Line gives the number j-1 The basic data of the items , Each row has 3 Nonnegative integers v p q

（ among v Indicates the price of the item （ v<10000 ）, p Indicates the importance of the item （ 1 ~ 5 ）, q Indicates whether the item is a master or an accessory . If q=0 , It means that the article is the main component , If q>0 , It means that the article is an accessory , q Is the number of the main part ）

Output description ：
The output file has only one positive integer , It is the maximum value of the sum of the product of the price and importance of the goods that does not exceed the total amount of money （ <200000 ）.
Example 1
Input ：
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
Copy
Output ：
2200
Copy
Example 2
Input ：
50 5
20 3 5
20 3 5
10 3 0
10 2 0
10 1 0
Copy
Output ：
130
Copy
explain ：
From the first 1 OK, you can see the total money N by 50 And the number of items you want to buy m by 5;
The first 2 And the 3 Yes q by 5, Explain that they are all numbered 5 The attachment of the item ;
The first 4_{6 Yes q All for 0, It means that they are all main parts , Their numbers are 3}5;
Therefore, the maximum value of the sum of the product of the price and importance of an article is 101+203+20*3=130

Answer key

After the data is saved , By analyzing this problem, we find that it is a common knapsack problem ： Under the condition that the total amount of money is limited , Get the most value .
But in this problem , The existence of attachments affects the solution of our dynamic equations .
In the knapsack problem , set up dp[i][j] It means that the amount of money does not exceed j Under the condition of , For the former i The maximum value that can be obtained from the selection of products .
If j>price[i] dp[i][j]=max(dp[i][j-price[i]]+value[i],dp[i-1][j])
otherwise dp[i][j]=dp[i-1][j])
So how to deal with attachments , We know , The numbers here are all main parts , Therefore, the judgment of accessories can be added after each main component
dp[i][j]=max( Main parts , Main parts + The attachment 1, Main parts + The attachment 2, Main parts + The attachment 3, Buyer... No )

Code

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    
    int N,m;
    cin>>N>>m;
    N/=10;// Reduce the magnitude of the loop 
    vector<vector<int>> price(m+1, vector<int>(3, 0));// Price 
    vector<vector<int>> value(m+1,vector<int>(3,0));// value 
    vector<vector<int>> dp(m+1,vector<int>(N+1,0));
    for(int i=1;i<=m;i++)
    {
    
        int v,p,q;
        cin>>v>>p>>q;
        v/=10;
        p*=v;
        if(q==0)// Main parts 
        {
    
            price[i][0]=v;
            value[i][0]=p;            
        }
        else{
    // First attachment 
            if(price[q][1]==0)
                {
    
                price[q][1]=v;
                value[q][1]=p;
                 }
            else{
    
                price[q][2]=v;
                value[q][2]=p;
                }
        }
        
    }
    // Start dynamic planning 
    for(int i=1;i<=m;i++)
        for(int j=1;j<=N;j++)
        {
    
            if(j>=price[i][0])// You can buy pieces 
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-price[i][0]]+value[i][0]);
            else dp[i][j]=dp[i-1][j];
            if (j >= price[i][0] + price[i][1]) {
     
                dp[i][j] = max(dp[i - 1][j - price[i][0] - price[i][1]]  + value[i][0] +  value[i][1],  dp[i][j]);
            }
            // You can buy pieces  +  The second attachment 
            if (j >= price[i][0] + price[i][2]) {
     
                dp[i][j] = max(dp[i - 1][j - price[i][0] - price[i][2]]  + value[i][0] + value[i][2],  dp[i][j]);
            }
             // You can buy pieces  +  Two attachments 
            if (j >= price[i][0] + price[i][1] + price[i][2]) {
     
                 dp[i][j] = max(dp[i - 1][j - price[i][0] - price[i][1] - price[i][2]]  + value[i][0] + value[i][1] + value[i][2],  dp[i][j]);
            }             
            
            
        }
    cout<<dp[m][N]*10;
    return 0;
}