ACM. Hj16 shopping list ●●

HJ16 Shopping list ●●

describe

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 ：

If you want to buy items classified as accessories , You must buy the main part of the accessory first , And each item You can only buy it once .

Each main component can have 0 individual 、 1 Or 2 Attachments . Attachments no longer have their own attachments .

Wang Qiang found the price of each item （ All are 10 An integral multiple of one yuan ）, And he only N Yuan budget . besides , He set an importance level for each item , Integers 1 ~ 5 Express . He hopes to spend no more than N Under the premise of yuan , Make your own Maximum satisfaction .

Satisfaction degree It refers to the... Of each item purchased The product of price and importance Of The sum of the , Let's assume that $i$ The price of the item is $v[i]$, The importance is $w[i]$, A total of $k$ Item , The serial numbers are $j_1,j_2,...,j_k$, Then the satisfaction is ：$v[j_1]\ast w[j_1]+v[j_2]\ast w[j_2]+\dots +v[j_k]\ast w[j_k]$.

Please help Wang Qiang calculate the maximum satisfaction .

Input description ：

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

（ among N （ N<32000 ） Express Total money , m （m <60 ） For purchasable The number of items .）

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 of the item Price （ v<10000 ）, p Indicates the of the item Importance （ 1 ~ 5 ）, q Indicates whether the item is a master or an accessory .
If q=0 , Indicates that the item is Main parts , If q>0 , It means that the article is an accessory , q yes Number of the main part ）

Output description ：

Output a positive integer , For the greatest satisfaction Zhang Qiang can get .

Example

Input ：
50 5
20 3 5
20 3 5
10 3 0
10 2 0
10 1 0
Output ：
130
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 10 * 1 + 20 * 3 + 20 * 3 = 130

Answer key

1. Dynamic programming （01 knapsack ）

0-1 knapsack problem
Problem description ： There is a backpack with a total weight of W, existing N Items , In each item w[i], value v[i], Pack the goods on the back , What is the maximum value that can be installed ？
Define the state transition array dp[i][j], Before presentation i Items , The weight of the backpack is j The maximum value that can be installed in the case of .
The equation of state transfer is ：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
I.e. the current No i Items Or put it in your backpack , Or don't put it in your backpack .

The nature of the shopping list problem is still 01 knapsack problem , It just adds the relationship between the main part and the accessories , If you don't see the attachment , Then it's with 01 The knapsack problem is the same ; The purchase of accessories here depends on the main parts .

So there are many different situations to consider ：
1、 Buyer... No （ And accessories ）;
2、 Only buy the main part ;
3、 Buyer parts + The attachment （ There are many situations ）.

Because there are at most 2 Attachments , So when entering data , Special processing of data , Place the attachment after the corresponding master array , Highlight dependencies ;
At the same time, the price and quantity are divided by 10, Reduce the amount of calculation ; In addition, the satisfaction can be （ Price * Importance ） Precomputation is stored in an array

We can think of it this way , For the same item , Now its price 、 Importance is variable ;
Then we only need to try the following four cases for each main component ：

1. Only one main part is added ;
2. Add the main part and the first attachment ;
3. Add the main part and the second attachment ;
4. Add the main part and two accessories ;

w[i][k] It means the first one i Item number k In this case ,k Value range of 0~3, Corresponding to the above four situations respectively ,v[i][k] It means the first one i Items correspond to the k The value of these situations , Now turn the shopping cart problem into 0-1 knapsack problem , That is, find the maximum value in the above four cases .

1. dp[i][j] To express with j * 10 Yuan purchase i Main components （ Including its attachments ） The greatest satisfaction you get when you get something in ;

2. dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i][k]]+v[i][k])
dp[i-1][j] Indicates that the current item is not put into the backpack ,w[i][k] It means the first one i The first main part corresponds to the k Medium condition , I.e. the current No i Of the four items, the one with the greatest value is either put into the backpack , Or don't put it in your backpack .
   namely dp[i][j] = max( Items are not put into the backpack , Main parts , Main parts + The attachment 1, Main parts + The attachment 2, Main parts + The attachment 1+ The attachment 2)

3. Initialize to 0;

4. The outer layer is the number of main items , The inner layer is the amount that can be spent .

• Time complexity ：$O(m\ast N)$, Double loop
• Spatial complexity ：$O(m\ast N)$, Need a two-dimensional extra array

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    
    int money, n;
    while(cin >> money >> n){
    
        vector<vector<int>> things(n, vector<int>(6, 0));
        money /= 10;                                  //  The amount is uniform  / 10, Reduce the calculation 
        int masterNum = 0;                            //  Quantity of main parts 
        for(int i = 0; i < n; ++i){
    
            int cost, important, master;
            cin >> cost >> important >> master;
            if(master == 0){
                              //  Main parts 
                things[i][0] = cost/10;
                things[i][1] = important * cost;      //  Item satisfaction is calculated in advance , Reduce the number of multiplications 
                ++masterNum;
            }else if(things[master-1][2] == 0){
           //  The attachment 1  Add to the main component array 
                things[master-1][2] = cost/10; 
                things[master-1][3] = important * cost;
            }else{
                                        //  The attachment 2  Add to the main component array 
                things[master-1][4] = cost/10;
                things[master-1][5] = important * cost;
            }
        }
        vector<vector<int>> dp(masterNum+1, vector<int>(money+1, 0));    //  Dynamic programming array 
        int masterIndex = 0;                        
        for(int i = 0; i < n; ++i){
    
            if(things[i][0] == 0) continue;         //  Non main parts , skip 
            ++masterIndex;                          //  Only traverse the main part , Record the main part index 
            for(int j = 1; j <= money; ++j){
    
                int masterCost = things[i][0];      //  cost 
                int attCost1 = things[i][2];
                int attCost2 = things[i][4];
                int masterSat = things[i][1];       //  Satisfaction degree 
                int attSat1 = things[i][3];
                int attSat2 = things[i][5];

                if(j >= masterCost){
                    //  Consider the main components first , buy   or   Not buy 
                    dp[masterIndex][j] = max(dp[masterIndex-1][j-masterCost] + masterSat, 
                                                    dp[masterIndex-1][j]);
                }else{
    
                    dp[masterIndex][j] = dp[masterIndex-1][j];		//  This step is also related to dp[masterIndex-1][j] Compare 
                }
    
                if(attCost1 > 0 && j >= masterCost + attCost1){
        //  Consider the main components + The attachment 1 Combine , buy   or   Not buy 
                    dp[masterIndex][j] = max(dp[masterIndex-1][j-masterCost-attCost1] + masterSat + attSat1, 
                                                    dp[masterIndex][j]);
                }else{
    
                    dp[masterIndex][j] = dp[masterIndex][j];
                }

                if(attCost2 > 0 && j >= masterCost + attCost2){
        //  Consider the main components + The attachment 2 Combine , buy   or   Not buy 
                    dp[masterIndex][j] = max(dp[masterIndex-1][j-masterCost-attCost2] + masterSat + attSat2, 
                                                    dp[masterIndex][j]);
                }else{
    
                    dp[masterIndex][j] = dp[masterIndex][j];
                }

                if(attCost2 > 0 && j >= masterCost + attCost1 + attCost2){
        //  Consider the main components + The attachment 1+ The attachment 2 Combine , buy   or   Not buy 
                    dp[masterIndex][j] = max(dp[masterIndex-1][j-masterCost-attCost1-attCost2] + masterSat + attSat1 + attSat2, 
                                                    dp[masterIndex][j]);
                }else{
    
                    dp[masterIndex][j] = dp[masterIndex][j];
                }  
            }    //  The resulting  dp[i][j] = max( Items are not put into the backpack , Main parts , Main parts + The attachment 1, Main parts + The attachment 2, Main parts + The attachment 1+ The attachment 2)
            if(masterIndex == masterNum) break;        //  The main component has been traversed 
        }
        cout << dp[masterNum][money] << endl;
    }

    return 0;
}

• One dimensional rolling array optimization O(m)

1. dp[j] Express j * 10 The maximum satisfaction that can be obtained by Yuan Shi ;
2. dp[j] = max(dp[j], dp[j-w[i]] + v[i]); among w[i] and v[i] There are four different situations
3. dp[0] = 0;
4. Let's start with the items , And then the amount , The amount goes from large to small .
   Traversing the amount in reverse order is to ensure that the items i Only once ！
   dp[j-w[i]]+v[i] When traversing in positive order, the previous value is updated , It will lead to repeated pick-up .

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    
    int money, n;
    while(cin >> money >> n){
    
        vector<vector<int>> things(n, vector<int>(6, 0));
        money /= 10;                                  //  The amount is uniform  / 10, Reduce the calculation 
        int masterNum = 0;                            //  Quantity of main parts 
        for(int i = 0; i < n; ++i){
    
            int cost, important, master;
            cin >> cost >> important >> master;
            if(master == 0){
                              //  Main parts 
                things[i][0] = cost/10;
                things[i][1] = important * cost;      //  Item satisfaction is calculated in advance , Reduce the number of multiplications 
                ++masterNum;
            }else if(things[master-1][2] == 0){
           //  The attachment 1  Add to the main component array 
                things[master-1][2] = cost/10; 
                things[master-1][3] = important * cost;
            }else{
                                        //  The attachment 2  Add to the main component array 
                things[master-1][4] = cost/10;
                things[master-1][5] = important * cost;
            }
        }
        vector<int> dp(money+1, 0);    //  Dynamic programming array 
        int masterIndex = 0;                        
        for(int i = 0; i < n; ++i){
    
            if(things[i][0] == 0) continue;         //  Non main parts , skip 
            ++masterIndex;                          //  Only traverse the main part , Record the main part index 
            for(int j = money; j >= 1; --j){
    		//  Reverse traversal ！！！
                int masterCost = things[i][0];      //  cost 
                int attCost1 = things[i][2];
                int attCost2 = things[i][4];
                int masterSat = things[i][1];       //  Satisfaction degree 
                int attSat1 = things[i][3];
                int attSat2 = things[i][5];

                if(j >= masterCost){
                    //  Consider the main components first , buy   or   Not buy 
                    dp[j] = max(dp[j-masterCost] + masterSat, dp[j]);
                }
    
                if(attCost1 > 0 && j >= masterCost + attCost1){
        //  Consider the main components + The attachment 1 Combine , buy   or   Not buy 
                    dp[j] = max(dp[j-masterCost-attCost1] + masterSat + attSat1, dp[j]);
                }

                if(attCost2 > 0 && j >= masterCost + attCost2){
        //  Consider the main components + The attachment 2 Combine , buy   or   Not buy 
                    dp[j] = max(dp[j-masterCost-attCost2] + masterSat + attSat2,  dp[j]);
                }

                if(attCost2 > 0 && j >= masterCost + attCost1 + attCost2){
        //  Consider the main components + The attachment 1+ The attachment 2 Combine , buy   or   Not buy 
                    dp[j] = max(dp[j-masterCost-attCost1-attCost2] + masterSat + attSat1 + attSat2, dp[j]);
                } 
            }    //  The resulting  dp[j] = max( Items are not put into the backpack , Main parts , Main parts + The attachment 1, Main parts + The attachment 2, Main parts + The attachment 1+ The attachment 2)
            if(masterIndex == masterNum) break;        //  The main component has been traversed 
        }
        cout << dp[money] << endl;
    }

    return 0;
}