Find the optimal set of weights to add to a certain set of weights

Question

In this challenge, you will recieve a comma-separated list of weights as input, such as

1,3,4,7,8,11

And you must output the smallest amount of weights that can add to that set. For example, the output for this set would be

1,3,7

Because you could represent all of those weights with just those three:

1     = 1
3     = 3
1+3   = 4
7     = 7
1+7   = 8
1+3+7 = 11

There may be more than one solution. For example, your solution for the input 1,2 could be 1,1 or 1,2. As long as it finds the minimum amount of weights that can represent the input set, it is a valid solution.

Weights may not be used more than once. If you need to use one twice, you must output it twice. For example, 2,3 is not a valid solution for 2,3,5,7 because you can't use the 2 twice for 2+2+3=7.

Input is guaranteed not to have duplicated numbers.

This is code-golf so shortest code by character count wins.

Network access is forbidden (so none of your "clever" wget solutions @JohannesKuhn cough cough) ;)

Simpleest cases:

1,5,6,9,10,14,15               => 1,5,9
7,14,15,21,22,29               => 7,14,15
4,5,6,7,9,10,11,12,13,15,16,18 => 4,5,6,7
2,3,5,7                        => 2,2,3 or 2,3,7

And some trickier ones:

10,16,19,23,26,27,30,37,41,43,44,46,50,53,57,60,61,64,68,71,77,80,84,87
  => 3,7,16,27,34
20,30,36,50,56,63,66,73,79,86
  => 7,13,23,43
27,35,44,46,51,53,55,60,63,64,68,69,72,77,79,81,86,88,90,95,97,105,106,114,123,132
  => 9,18,26,37,42

Answer 1

Mathematica 80 75

Update: See at bottom an update on Doorknob's challenging last test, added on Nov.5

---

This passes all but the last test. However, it does not attempt to use a digit more than once. And it only searches from solutions that are subsets of the larger data set.

The function generates all of the subsets of the input data set and then tests which subsets can be used to construct the complete set. After the viable subsets are found, it chooses the smallest sets.

s=Subsets
f@i_:=GatherBy[Select[s@i,Complement[i, Total /@ s@#]=={}&],Length]〚1〛

Tests

f[{1, 3, 4, 7, 8, 11}]

{{1, 3, 7}}

---

f[{1, 5, 6, 9, 10, 14, 15}]

{{1, 5, 9}}

---

f[{7, 14, 15, 21, 22, 29}]

{{7, 14, 15}}

---

f[{4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 18}]

{{4, 5, 6, 7}}

---

f[{2, 3, 5, 7}]

{{2, 3, 5}, {2, 3, 7}}

---

Update

Below I'll provide an initial analysis that may help get started toward a solution.

The data:

data = {10, 16, 19, 23, 26, 27, 30, 37, 41, 43, 44, 46, 50, 53, 57, 60, 61, 64, 68, 71, 77, 80, 84, 87};

Differently from the earlier approach, we want to consider, in the solution set, numbers that do NOT appear in the data set.

The approach makes use of absolute differences between pairs of numbers in the data set.

g[d_] := DeleteCases[Reverse@SortBy[Tally[Union[Sort /@ Tuples[d, {2}]] /. {a_, b_} :> Abs[a - b]], Last], {0, _}] 

Let's look at the number of times each difference appears; we'll only grab the first 8 cases, starting from the most common difference].

g[data][[1;;8]]

{{7, 14}, {27, 13}, {34, 12}, {3, 11}, {20, 10}, {16, 10}, {4, 10}, {11, 9}}

14 pairs differed by 7; 13 pairs differed by 27, and so on.

Now let's test subsets starting with {difference1},{difference1, difference2}, and so on, until we can hopefully account for all the original elements in the data set.

h reveals those numbers from the original set that cannot be constructed by composing sums from the subset.

h[t_] := Complement[data, Total /@ Subsets@t]

By the fifth try, there are still 10 elements that cannot be formed from {7, 27, 34, 3, 20}:

h[{7, 27, 34, 3, 20}]

{16, 19, 26, 43, 46, 53, 60, 77, 80, 87}

But on the next try, all numbers of the data set are accounted for:

h[{7, 27, 34, 3, 20, 16}]

{}

This is still not as economical as {3,7,16,27,34}, but it's close.

---

There are still some additional things to take into account.

1. If 1 is in the data set, it will be required in the solution set.
2. There may well be some "loners" in the original set that cannot be composed from the most common differences. These would need to be included apart from the difference tests.

These are more issues than I can handle at the moment. But I hope it sheds some light on this very interesting challenge.

Answer 2

Ruby 289

This is a straight enumeration, so it will obtain minimal solutions, but it may take years--possibly light years--to solve some problems. All the "simplest cases" solve in at most a few seconds (though I got 7,8,14 and 1,2,4 for the 3rd and 5th cases, respectively). Tricky #2 solved in about 3 hours, but the other two are just too big for enumeration, at least for the way I've gone about it.

An array of size n that generates the given array by summing subsets of its elements is of minimal size if it can be shown that there is no array of size < n that does that. I can see no other way to prove optimality, so I start the enumeration with subsets of size m, where m is a known lower bound, and then increase the size to m+1 after having enumerated subsets of size m and shown they none of those "span" the given array, and so on, until I find an optimum. Of course, if I have enumerated all subsets up to size n, I could use a heuristic for size n+1, so that if I found a spanning array of that size, I would know it is optimal. Can anyone suggest an alternative way to prove a solution is optimal in the general case?

I've included a few optional checks to eliminate some combinations early on. Removing those checks would save 87 characters. They are as follows (a is the given array):

• an array of size n can generate at most 2^n-1 distinct positive numbers; hence, 2^n-1 >= a.size, or n >= log2(a.size).ceil (the "lower bound" I referred to above).
• a candidate generating array b of size n can be ruled out if:
  • b.min > a.min
  • sum of elements of b < a.max or
  • b.max < v, where v = a.max.to_f/n+(n-1).to_f/2.ceil (to_f being conversion to float).

The last of these, which is checked first, implements

sum of elements of b <= sum(b.max-n+1..b.max) < a.max

Note v is constant for all generator arrays of size n.

I've also made use of @cardboard_box's very helful observation that there is no need to consider duplicates in the generating array.

In my code,

(1..a.max).to_a.combination(n) 

generates all combinations of the numbers 1 to a.max, taken n at a time (where a.max = a.last = a[-1]). For each combination b:

(1...2**n).each{|j|h[b.zip(j.to_s(2).rjust(n,?0).split('')).reduce(0){|t,(u,v)|t+(v==?1?u:0)}]=0}

fills a hash h with all numbers that are sums over non-empty subsets of b. The hash keys are those numbers; the values are arbitrary. (I chose to set the latter to zero.)

a.all?{|e|h[e]}}

checks whether every element of the given array a is a key in the hash (h[e] != nil, or just h[e]).

Suppose

n = 3 and b=[2,5,7].

Then we iterate over the range:

(1...2**8) = (1...8) # 1,2,..,7

The binary representation of each number in this range is used to stab out the elements of b to sum. For j = 3 (j being the range index),

3.to_s(2)                  # =>  "11"
"11".rjust(3,?0)           # => "011"
"011".split('')            # => ["0","1","1"]
[2,5,7].zip(["1","0","1"]) # => [[2,"0"],[5,"1"],[7,"1"]]
[[2,"0"],[5,"1"],[7,"1"]].reduce(0){|t,(u,v)|t+(v==?1?u:0)}]=0 # => t = 0+5+7 = 12 

The code:

x=a[-1]
n=Math.log2(a.size).ceil
loop do
v=(1.0*x/n+(n-1)/2.0).ceil
(1..x).to_a.combination(n).each{|b|
next if b[-1]<v||b[0]>a[0]||b.reduce(&:+)<x
h={}
(1...2**n).each{|j|h[b.zip(j.to_s(2).rjust(n,?0).split('')).reduce(0){|t,(u,v)|t+(v==?1?u:0)}]=0}
(p b;exit)if a.all?{|e|h[e]}}
n+=1
end