Submit | All submissions | Best solutions | Back to list |
HS08AKP - Another Knapsack Problem |
Given 1 < n < 100 000 items, select some of them in such a way that the total weight of the selected items is at most S (1 < S < 1 000 000 000). For each item i you are given its weight 0 < mi < S and its value 0 <= vi < 1000. The larger the value of selected items, the better. Can you obtain the optimal solution?
Input
First two positive integers, S and n. Then n lines follows. In the i-th line there are exactly two numbers, denoting the mass and value of the i-th item, respectively.
Output
In the first line output k - the number of items to be taken. Next, output their numbers with respect to the order given by the input.
Scoring
The score awarded to your program for a given test is computed as max{0, Vp - V}, where Vp is your program score, and V is a reference value (the result obtained by greedy approximation algorithm minus 10). The overall score of the program is the sum of scores obtained for the correctly solved tests.
The number of points given in the ranking is scaled so that it is equal to 10 for the registered contestant whose solution has the highest score, and proportionally less for all solutions with lower scores.
Example
Input: 4 5 1 8 2 4 3 0 1 5 2 3 Output: 2 1 4 Scoring: As V=7, the above solution scores max{0, 13 - 7} = 6 points.
Input data sizes
Approximate test data sizes are given below.
t n l 1 72100 2s 2 40000 2s 3 4000 2s 4 94100 2s 5 9000 2s t - testcase number n - the number of items l - time limit
Please note
Submissions will be visible to the submitting contestant, only, and tested on the full set of test cases.
Added by: | kuszi |
Date: | 2009-05-31 |
Time limit: | 0.400s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: CLOJURE NODEJS PERL6 VB.NET |
hide comments
2015-08-20 14:47:01 kuszi
This is an optimisation problem. There is no the only one correct answer - there are better and worse ones. |
|
2015-08-13 20:23:38
is the test case correct? the max value should be 17 for index 0,1,3 |