For each mass store amount of possibilities you can get it. If this
number exceeds to than you can lower it downto 2.
NumGet: array[0..MaxCardMass * MaxCards] of byte;

For each mass store atleast one (if possible) card wich can create
that mass.
WhatGet: array[1..MaxCardMass * MaxCards] of byte;

You need 1000*100 * 2 arrays of bytes.

Start DP with 0 cards;
NumGet[0] := 1;

for CurrentCard <- 1 to CardCount do
    for i <-SumOfAllCards - CardWeight[CurrentCard] DOWNTO (!!!) 0 do
      if NumGet[i] <> 0 then
         Inc(NumGet[i + CardWeight[CurrentCard]], NumGet[i]);
         if NumGet[i + CardWeight[CurrentCard]] > 2 the
              NumGet[i + CardWeight[CurrentCard]] := 2
         if WhatGet[i + CardWeight[CurrentCard]] = 0 then
              WhatGet[i + CardWeight[CurrentCard]] := CurrentCard;

Downto needed to avoid next trap:
consider we can get mass 100
know we check card with mass 10
when i = 100 we mark that we can get 110
when i = 110 and it is (already marked) we mark 120
when i = 120 ...
...

Hope this will be helpfull...

I have the same idea as you.but i got WA.Please help me.
I think we should check if there is no solution(output 0) first,and
then check if there is more than one solution(output -1). am I right?

Here is my program:

[code deleted]

Edited by moderator 27.03.2007 09:45

Knapsack at all, guys, as well :)

It's so helpfull...
Thank you.
:)