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
7,7,7,8
above), which increases complexity manyfold. \$\endgroup\$n
inputs weights andm
is the largest, enumerate all subsequences of(1..m)
and for each subsequence, enumerate every combination of between 1 andn
instances of each element of the sequence.) \$\endgroup\$