Combinations that give a specific number

I have a vector of numbers

A=[5384
87648
266235
123701
79553
79037
24999
386311
108999
194543
167064
88139
0
226190
13902
483786
10003
33183];

How can I tell which combination gives the exact number 652890 . In other words, I now that a combination of few numbers of vector A should give 652890 as an answer but I don't know which. How can I find the combination ? (most probably I need only + and - functions )

Answer 1

[John D'Errico]

(Yes, this is a knapsack problem.) It can also be solved using a recursive programming tool. Or we could have used a integer programming tool. I'll show how to do it using the recursive tool.

If you constrain these integers to appear exactly once and no more than that, then there is no combination of those numbers that will suffice.

The simple (recursive) solution is to use my partitions function, as found on the file exchange. It operates recursively to solve the problem. The third argument tells it the maximum number of replicates allowed for any member of the set.

partitions(652890,sort(A),1)
ans =
   Empty matrix: 0-by-18

partitions(652890,sort(A),2)
ans =
   Empty matrix: 0-by-18

As you can see, until I allow 3 replicates, no solution is returned.

sort(A)
ans =
   0 5384 10003 13902 24999 33183 79037 79553 87648 88139 108999 123701 167064 194543 226190 266235 386311 483786

partitions(652890,sort(A),3)
ans =
  0  1  1  0  0  0  3  1  0  1  1  1  0  0  0  0  0  0
  0  2  1  2  3  1  0  0  2  1  1  1  0  0  0  0  0  0
  0  2  2  1  0  0  3  0  0  0  0  3  0  0  0  0  0  0
  0  2  3  2  0  3  1  3  0  0  0  0  1  0  0  0  0  0
  0  0  1  1  0  3  0  2  1  1  0  0  0  1  0  0  0  0
  0  2  0  1  0  3  0  0  0  0  0  0  2  1  0  0  0  0

Each row of the above array indicates one solution, where a non-zero value corresponds to the multiplicity of the corresponding element of your set. For example, the first row of this array denotes the sum...

5384 + 10003 + 79037 + 79037 + 79037 + 79553 + 88139 + 108999 + 123701
ans =
    652890

See that 79037 appeared 3 times in that sum. Pick any row to find a distinct solution, so there are 6 possible solutions with exactly 3 replicates, and none with less than 3 reps.

Of course, if you allow negative amounts of those integers, we might find a simpler answer.

Edit: Just for kicks, lets see how one would solve this problem using another tool, here intlinprog.

intlinprog(ones(1,18),1:18,[],[],sort(A)',652890,zeros(1,18),[])
LP:                Optimal objective value is 1.437741.                                             

Cut Generation:    Applied 1 clique cut, 2 implication cuts,                                        
                   and 2 strong CG cuts.                                                            
                   Lower bound is 2.001292.                                                         

Branch and Bound:

     nodes     total   num int        integer       relative                                          
  explored  time (s)  solution           fval        gap (%)                                         
      4603      0.20         1   1.700000e+01   6.111111e+01                                          
      6607      0.29         2   9.000000e+00   2.000000e+01                                          
     16607      0.68         2   9.000000e+00   1.000000e+01                                          
     17383      0.70         2   9.000000e+00   0.000000e+00                                          

Optimal solution found.

Intlinprog stopped because the objective value is within a gap tolerance of the optimal value, options.TolGapAbs = 0 (the default value). The intcon
variables are integer within tolerance, options.TolInteger = 1e-05 (the default value).

ans =
                         0
                         1
                         1
                         0
                         0
                         0
                         3
                         1
                         0
                         1
                         1
                         1
                         0
                         0
                         0
                         0
                         0
                         0

That should be one of the 6 possible solutions that partitions found. In fact, it looks like the first one in my set of 6 solutions.

Answer 2

[Cristiano]

Your problem has a name, it's the Knapsack problem. Although I cannot help you with the solution, I point you the direction:

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

Good luck!