IITKESO207SPA3B - Knapsack Problem

This problem deals with the simple knapsack problem.

You are required to find the set of of items that goes into the knapsack for which the value is maximized. The input will contain the number of items, value, space taken up by each item, and the total capacity of the knapsack.

Input

The input will contain three lines. The first line will an integer n, which is the number of items you have to consider. The second line will contain n pairs of space, value each indicating how much it costs to put the item inside the knapsack, and how much value it has for the knapsack. The third line will contain a single integer, C that is the total capacity of the knapsack.

Output

You are required to print m space separated integers, which are in non decreasing order, of the item costs that will be put in the knapsack for maximum value. (The items must add up to be less than or equal to the knapsack capacity).

Example

Input:
10
2 3 4 3 8 3 2 3 4 3 10 3 12 3 7 3 9 3 15 3
19

Output:
2 2 4 4 7

Scoring method

Please note that apart from the sample test case posted here, there will be other hidden test cases that your code will checked on. The final score you see is a percentage of the test cases you have passed. If you pass only the sample test case, you will get 0/100 (even though your score will be shown as 10/100).

Each of these questions are finally worth the points mentioned in the assignment pdf file. So your credit for this problem shall be your score/100 * points for this question. Your final credit for programming assignment 3 shall be final score / 55 * 100.

Plagiarism and Copying

Strict action will be taken against students who are found to be indulging in plagiarism. Please note that changing variable names, removing indentation or moving code around will not help with regards to plagiarism checking.


Added by:Programming Club, IITK
Date:2017-06-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:ESO207, IIT Kanpur Summer Semester 2017

hide comments
2019-11-22 21:01:14
is there any submission link?
2017-06-30 15:22:42
@pawanrocks
your query:
4
2 4 2 4 4 8 2 4
6
print 2 2 2
and not 2 4
ie if you arrange the capacities in ascending order, you should print 1st non decreasing solution.
stop listening to people who are giving ascending logic(because there could be cases having more than one ascending solution too). would waste your time.

Last edit: 2017-06-30 15:24:15
2017-06-29 21:44:21
Sample:
5
1 8 2 4 3 0 2 5 2 3
4

The answer is:
1 2
2017-06-29 21:25:54
In knapsack, we consider items one by one. So, in case there are multiple solutions, print that solution which you discovered first (in this case 2 4).

Last edit: 2017-06-29 21:30:48
2017-06-29 18:07:56
A sample test case would be helpful
2017-06-29 14:55:57
The question asks to print in non decreasing order; 2 2 2 and 2 4 are two possible solutions with volume equal to 12.
2017-06-29 14:37:07
2 4
as it is in increasing order


Last edit: 2017-06-29 14:37:44
2017-06-29 13:08:23
What should I print for the following case:
4
2 4 2 4 4 8 2 4
6
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.