BACKPACK - Dab of Backpack
One day Blue Mary goes to a nearby supermarket to buy some goods. She has a backpack, whose capacity is V-Max. She finds that there are many goods in the market, each has a volume Vi(it will always be a multiple of 10 and less than 10000) and an importance Ci(1<= Ci <=5). Since she has almost unlimited money, the only problem she is to solve is how to choose goods such that the total volume won't exceed the capacity of the backpack and the sum of the product of the volume and the importance of each good is maximum. To be an excellent mathematician, she comes up with the answer quickly, and now she wants you to do a harder task. There are two kinds of goods: main goods and attachments. If you want to buy an attachment you must buy its main good before.
Multiple test cases, the number of them is given in the very first line.
For each test case:
The first line contains two space-separated integers V-Max (1<=V-Max<=32000) and the number of the goods N (1<=N<=60). N lines follow, each contains three space-separated integers Vi, Ci and a integer u. If u is not 0, this good is an attachment of good u(as the order in the input file).
To make the problem not too difficult, Blue Mary tells you that:
(A) An attachment won't have any attachments which belong to it.
(B) A main good will always have less than 3 attachments.
For each test case:
The first and the only line contains a single integer denoted the answer.
Input: 1 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 Output: 2200
Finally got AC, very good problem thanks to the problemsetter
finally got AC.....after trying too hard...nice problem...:)
@ankit You can buy as many attachments as you want, even no one , but satisfying the condition that you have bought their main good !
Are the goods unbounded or single(limited) , pls mention it
can i buy a particular attachment and the main good..???
Plz explain the questn properly! Are repetitions allowed?
@cenation : no
if we take a main good are we forced to take its attachments also??
very nice problem