Knapsack 5 - MarisaOJ: Marisa Online Judge

There are

$n$ items,

$i^{th}$ item has the weight of

$w_i$ and value of

$v_i$ . You can choose an arbitrary number items as long as their weight doesn't exceed a given

$S$ . Find a way of choosing items so that their value is maximum possible. ### Input - First line contains 2 integers

$n$ and

$S$ . - Each line in the next

$n$ line contains 2 integers

$w_i$ ,

$v_i$ . ### Output - The first contains the maximum possible value you can obtain and

$k$ , the number of the selected items. - The second line contains

$k$ integers, the indices of the selected items, can be in any order. ### Constraints -

$1 \le n \le 100, S \le 10^{12}$ . -

$1 \le w_i, v_i \le 10^{12}$ . ### Example Input:

$3 5 1 4 4 1 2 100$

Output:

$104 2 1 3$

### Scoring - All test cases are scored equally. - Consider the jury's answer as

$Y$ and your answer as

$X$ . - If

$X \ge Y$ , you receive a score of

$100\\%$ for test case. - If

$1 < \frac{Y}{X} \le 1.5$ , your score for the test case is calculated as

$(\frac{3X - 2Y}{X})^5\times 100 \\%$ . - If

$\frac{Y}{X} > 1.5$ , you receive a score of

$0\\%$ for the test case.

Introduction to Heuristic
	Travelling Salesman Problem 3
	Custom keyboard 2
	Maximum clique
	Superstring 2
	Knapsack 5
	Min-Max mTSP

Topic

Heuristic

Rating

2100

Solution (0)

Solution