Knapsack problem with answer recovery
Problem
Given N items of mass m1, …, mN and cost c< sub>1, …, cN respectively.
They fill a backpack that can withstand a weight of no more than M. Determine the set of items that can be carried in a backpack that has the highest cost.
Input:
- the first line contains a natural number N not exceeding 100 and a natural number M not exceeding 10000;
- on the second line enter N natural numbers mi not exceeding 100;
- N natural numbers withi not exceeding 100 are entered in the third line.
Output: print the numbers of items (numbers from 1 to N) that will be included in the backpack of the highest cost (one number per line).
Examples
| # |
Input |
Output |
| 1 |
4 6
2 4 1 2
7 2 5 1
|
1
3
4 |