(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.
