Title Link

487. Jin Ming's budget plan

Jinming is very happy today. He needs the key to the new house he bought at home. There is a very spacious room dedicated to Jinming himself.

Even more pleased with him, his mother said to him yesterday, "what items do you need to buy and how to arrange your room? You has the final say, if you don't exceed RMB N\."

Early this morning, Jin Ming began to make a budget. He divided the items he wanted to buy into two categories: main parts and accessories. Accessories are subordinate to a certain main part. The following table shows some examples of main parts and accessories:

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 \) attachments.

The attachment no longer has its own attachment.

Jin Ming wants to buy a lot of things, which will certainly exceed his mother's limit of \ (N \) yuan.

Therefore, he specified an importance degree for each item, which is divided into \ (5 \) and so on: expressed by integer \ (1 ~ 5 \), the fifth is the most important.

He also found the price of each item on the Internet (which is 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 \ (J \) article be \ (v[j] \) and its importance be \ (w[j] \), and a total of \ (K \) articles are selected and numbered \ (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 a multiplication sign)

Please help Jin Ming design a shopping list that meets the requirements.

Input format

Line \ (1 \) of the input file is two positive integers separated by a space: \ (N m \), where \ (N \) represents the total money and \ (m \) 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 \), and each line has \ (3 \) non negative integers v p q, where \ (V \) represents the price of the article, \ (P \) represents the importance of the article (\ (1 ~ 5 \)), and \ (Q \) represents whether the article is the main or accessory.

If \ (q=0 \), it means that the item is the main part. If \ (Q > 0 \), it means that the item is an accessory, and \ (Q \) is the number of the main part.

Output format

The output file has only one 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 amount of money.

Data range

\(N<32000,m<60,v<10000\)

Input sample:

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

Output example:

2200

Problem solving ideas

Group Backpack

There are at most two attachments, that is, if they are expressed in binary, there are four cases: \ (00,01,10,11 \), and one of these cases \ (4 \) is transformed into a grouping knapsack problem

• Time complexity: \ (O(2^2nV) \)

code

// Problem: Jin Ming's budget plan
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/489/
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=32005;
int f[N],V,n,m;
PII master[N];
vector<PII> servent[N];
int main()
{
    cin>>V>>n;
    for(int i=1;i<=n;i++)
    {
    	int v,p,q;
    	cin>>v>>p>>q;
    	p*=v;
    	if(q)servent[q].pb({v,p});
    	else
    		master[i]={v,p};
    }
    for(int i=1;i<=n;i++)
    {
    	for(int j=V;~j;j--)
    	{
    		for(int k=0;k<1<<servent[i].size();k++)
    		{
    			auto [v,w]=master[i];
    			
    			for(int t=0;t<servent[i].size();t++)
    				if(k>>t&1)
    				{
    					v+=servent[i][t].fi;
    					w+=servent[i][t].se;
    				}
    			
    			if(j>=v)f[j]=max(f[j],f[j-v]+w);
    		}
    	}
    }
    cout<<f[V];
    return 0;
}