Knapsack with Masses#4832
Given items, where each item has a mass m_1, m_2, \ldots, m_n and a cost c_1, c_2, \ldots, c_n, respectively.
You are to fill a knapsack that can withstand at most units of weight. Find a set of items to include in the knapsack such that their total weight does not exceed and their total cost is maximized.
The first line contains a positive integer (1 \le s \le 10^4) — the capacity of the knapsack.
The second line contains (1 \le n \le 100) positive integers m_i (1 \le m_i \le 100) — the weights of the items.
The third line contains positive integers c_i (1 \le c_i \le 100) — the costs of the items.
Print the indices of the items (numbers from to ) that should be included in the knapsack such that the total cost is maximized.
Example 1