IITKESO207SPA3B  Knapsack Problem
Problem description
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 format
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 format
You are required to print m space seperated integers, which are in non decreasing order, of the item costs that will be put in the knapsack for maximum value. (The costs must add up to be less than or equal to the knapsack capacity).
Sample input
10 2 3 4 3 8 3 2 3 4 3 10 3 12 3 7 3 9 3 15 3 19
Sample 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.
hide comments
account21:
20170630 15:22:42
@pawanrocks


rahulmpm:
20170630 00:59:10
Last edit: 20170630 00:59:49 

carlosmendes_7:
20170629 21:44:21
Sample:


alpha_codeboy:
20170629 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: 20170629 21:30:48 

vjindal:
20170629 18:07:56
A sample test case would be helpful 

pawanrocks:
20170629 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. 

namanh07:
20170629 14:37:07
2 4


pawanrocks:
20170629 13:08:23
What should I print for the following case:

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