Title Description:

Wang Qiang is very happy today. The company gives a year-end bonus of N 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. Accessories are subordinate to a main part. The following table is an example of some main parts and accessories:

Main parts	enclosure
computer	Printer, scanner
Bookcase	books
desk	Desk lamp, stationery
Work chair	nothing

If you want to buy an item classified as an accessory, you must first buy the main part to which the accessory belongs. Each master can have 0, 1, or 2 accessories. The attachment no longer has its own attachment. Wang Qiang wants to buy a lot of things. In order not to exceed the budget, he sets an importance degree for each item, which is divided into ， 5 ， and so on: expressed by integers ， 1 ~ 5 ， and ， 5 ， is the most important. He also found the price of each item on the Internet (an integral multiple of {10} yuan). He hopes to maximize the sum of the product of the price and importance of each item on the premise that it does not exceed ＾ N ＾ yuan (which can be equal to ＾ N ＾ yuan).

Let the price of the article J be v[j] and the importance be w[j]. A total of k articles are selected, and the numbers are j 1, j 2,..., J k, then the sum is:

v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] . (where * is the multiplication sign)

Please help Wang Qiang design a shopping list that meets the requirements

Enter Description:

Line 1 ＾ of the input is two positive integers separated by a space: N ＾ m

(where N (< 32000) is the total money, and m (< 60) is the number of items you want to buy.)

From line ＾ 2 ＾ to line ＾ m+1 ＾ line ＾ j ＾ gives the basic data of the article numbered ＾ j-1 ＾ with ＾ 3 non negative integers ＾ v ＾ p ＾ q in

(where  v  indicates the price of the article (v < 10000), p  indicates the importance of the article (1 ~ 5), and Q  indicates whether the article is a main part or an accessory. If ﹤ q=0, it means the article is the main part; if ﹤ Q > 0, it means the article is an accessory, and Q ﹤ is the number of the main part)

Output Description:

The output file has only a positive integer, which is the maximum value (< 200000) of the sum of the product of the price and importance of the goods that do not exceed the total money.

Example:

Input:

1000 5

800 2 0

400 5 1

300 5 1

400 3 0

500 2 0

Output:

2200

Problem solving ideas:

This problem is a dynamic programming problem, similar to the knapsack problem, that is, to explore how to pack can maximize the use.

First, you can place the entered item information in the array. There are three item types: entity, attachment 1 and attachment 2. If you buy an attachment, you must buy the corresponding entity, that is, at least one item in the purchase scheme is an entity; Considering the situations of only the buyer, the buyer + Annex 1, the buyer + Annex 2, the buyer + Annex 1 + Annex 2, select the scheme that maximizes the value of all purchase schemes for a certain amount of money, and take its value as the maximum value under the amount of money, that is, dp[N], N is the value of money. dp[j-ZJ_Pri[i] ] + ZJ_ Imp [i] refers to the value when the i-th entity is placed. If this value is higher than the current dp[j], replace dp[j], which plays the role of dynamic adjustment and always makes dp[j] the maximum value in the traversed scheme.

Among them, Pri is the price of goods, and Imp is the price of goods multiplied by importance; Under dynamic programming, we must use reverse order traversal; The reason for dividing by 10 is to improve the calculation speed.

The test code is an excellent C + + case in niuke.com, which is more concise and clear than my own implementation. The author's nickname: I don't know what's his name 123. The boss of Tsinghua is really powerful ~ it is promoted to everyone for learning and reference.

Test code:

#include<iostream>
#include<vector>
using namespace std;
int max(int m, int n)
{
    return m>n?m:n;
}
int dp[3200];
int main()
{
    int N,n,v,p,q;
    cin >> N >> n;
    N = N/10;
 
    int *ZJ_Pri = new int[n+1]();  int *ZJ_Imp = new int[n+1]();
    int *FJ1_Pri = new int[n+1](); int *FJ1_Imp = new int[n+1]();
    int *FJ2_Pri = new int[n+1](); int *FJ2_Imp = new int[n+1]();
 
    for(int i=1; i<=n; i++)
    {
        cin >> v >> p >> q;
        v = v / 10;
        if(q == 0)
        {
            ZJ_Pri[i] = v;
            ZJ_Imp[i] = v * p;
        }
        else if(FJ1_Pri[q] == 0)
        {
            FJ1_Pri[q] = v;
            FJ1_Imp[q] = v * p;
        }
        else
        {
            FJ2_Pri[q] = v;
            FJ2_Imp[q] = v * p;
        }
    }
    for(int i = 1; i <= n; i++)//i --- first i items
    {
        for(int j = N; j >=1; j--)//j -- current amount of money
        {
 
            if(j >= ZJ_Pri[i])
                dp[j] = max(dp[j], dp[ j-ZJ_Pri[i] ] + ZJ_Imp[i]);
            if(j >= ZJ_Pri[i] + FJ1_Pri[i])
                dp[j] = max(dp[j], dp[ j-ZJ_Pri[i]-FJ1_Pri[i] ] + ZJ_Imp[i] + FJ1_Imp[i]);
            if(j >= ZJ_Pri[i] + FJ2_Pri[i])
                dp[j] = max(dp[j], dp[ j-ZJ_Pri[i]-FJ2_Pri[i] ] + ZJ_Imp[i] + FJ2_Imp[i]);
            if(j >= ZJ_Pri[i] + FJ1_Pri[i] + FJ2_Pri[i])
                dp[j] = max(dp[j], dp[ j-ZJ_Pri[i]-FJ1_Pri[i]-FJ2_Pri[i] ] + ZJ_Imp[i] + FJ1_Imp[i] + FJ2_Imp[i]);
        }
    }
    cout << dp[N]*10 << endl;
 
    delete[] ZJ_Pri;
    delete[] ZJ_Imp;
    delete[] FJ1_Pri;
    delete[] FJ1_Imp;
    delete[] FJ2_Pri;
    delete[] FJ2_Imp;
 
    return 0;
}