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 < m_{i} < S and its value 0 <= v_{i} < 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 ith line there are exactly two numbers, denoting the mass and value of the ith 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, V_{p}  V}, where V_{p} 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:  20090531 
Time limit:  0.400s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: CLOJURE NODEJS PERL6 VB.NET 
hide comments
20150820 14:47:01 kuszi
This is an optimisation problem. There is no the only one correct answer  there are better and worse ones. 

20150813 20:23:38
is the test case correct? the max value should be 17 for index 0,1,3 