Knapsack like problem. Please heellpp as fast as possible!

[rausted]

I have a problem that I cannot solve! This problem is for a competition in Greece, so if you have any ideas please report before new years eve.
Here is the problem:

We want to built a stone monument or something, and we need to find the best amount of stones to do this. The input has in the first line two numbers
S=the area and N=the number of stones. All numbers are in integer limits.
the lines 2 to n+1 have one number which is the area of each stone. Please find me an algorithm faasstt! Its similar to knapsack problem because the less stones are used the better, but its different because the final result must be the closest to S sum of stone areas. Any ideas are welcome! Start posting whatever you think!

sample input: the_wall.in
10 100
40
22
11
20
9
8
6
2
3
4
solution: 40+22+11+20+4+3

[jim enright]

this is a known class of problems solveable by integer programmin software and techniques. there is a brute force solution for small numbers of choices:

set up 0/1 indicaters to represent the exclusion/inclusion of the particular stone in the set of stones being used.

set up an incumbent solution of all stones not included and 0 area

set up the requisite number of "for" loops (going from 0 to 1) and run through every combination of 0/1 and evalute the set of include stones:

compare to the current solution to the inumbent solution:

if the are covered is greater than the incumbent area then record the
0/1 settings as the new incumbent solution

if the are covered is the same as the incumbent solution then check to see if
less stones are used - if so reset the incumbent solution

[rausted]

n<=1000, so the brute force is not good. I need a dynamic programming solution. Please report a pseudo code or code in pascal or delphi or C.

[MrViggy]

Start with the knapsack algo, and modify it from there (?):

http://en.wikipedia.org/wiki/Knapsack_problem

Viggy

[jim enright]

??????

the smaller the number of stones - the more applicable the user of brute force!