Hj16 shopping list

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 instructions ：

 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 10*1+20*3+20*3=130  

The test case passed , When submitting the following set of data, the answer is 3900, But manual calculation is 3500

1000 5
300 5 0
400 2 0
300 5 2
300 4 2
600 4 0

Optimization welcome ~

#include<bits/stdc++.h>
using namespace std;

// List of each item entered 
struct Node {
    int Val;       // The unit price 
    int Money;     //  The unit price * The weight   The sum of the 
};

//  The unit price * Weight ranking 
bool cmp(Node node1, Node node2)
{
    return node1.Money > node2.Money;
}

int main()
{
    int money, Num, count = 0;
    cin >> money >> Num;
    int i = Num;

    // Definition Num An array of structures 
    Node* node = new Node[Num];
    for (int i = 0; i < Num; i++)
    {
        node[i].Val = 0;
        node[i].Money = 0;
    }

    while (i)
    {
        int val, weight, num;
        cin >> val >> weight >> num;
        // assignment 
        if (num == 0)
        {
            node[Num - i].Val += val;
            node[Num - i].Money += val * weight;
        }
        else
        {
            node[num - 1].Val += val;
            node[num - 1].Money += val * weight;

        }

        i--;
    }
    // Sort by total value from large to small 
    sort(node, node + Num, cmp);
    //i = 0;
    for (int j = 0;j < Num; j++)
    {
        if (i + node[j].Val > money)
            continue;
        else  
        {
            i += node[j].Val;
            count += node[j].Money;
        }     
    }
    cout << count;
    return 0;
}