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.
hide comments
sleepy_coder:
2019-11-22 21:01:14
is there any submission link? |
|
account21:
2017-06-30 15:22:42
@pawanrocks
|
|
carlosmendes_7:
2017-06-29 21:44:21
Sample:
|
|
alpha_codeboy:
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 |
|
vjindal:
2017-06-29 18:07:56
A sample test case would be helpful |
|
pawanrocks:
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. |
|
namanh07:
2017-06-29 14:37:07
2 4
|
|
pawanrocks:
2017-06-29 13:08:23
What should I print for the following case:
|
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 |