# Finding the sum closest to a target number

Wallace the Weightlifting Walrus is training for a contest where it will have to lift 1000 kg. Wallace has some weight plates lying around, possibly of different weights, and its goal is to add some of the plates to a bar so that it can train with a weight as close as possible to 1000 kg.

In case there exist two such numbers which are equally close to 1000 (e.g. 998 and 1002), Wallace will pick the greater one (in this case 1002).

Help Wallace the Weightlifting Walrus and tell it which weight it will have to lift.

## Input

The first line of the input contains the number of plates n (1≤ n ≤ 1000). Each of the following n lines contains one positive integer less than or equal to 1000, denoting the weight of each plate.

## Output

Output one integer, the combined weight closest to 1000.

https://open.kattis.com/problems/walrusweights

e.g if n = [4, 900, 500, 498, 4], the output will be 1002

var input = [4, 900, 500, 498, 4];
function walrusWeight(input) {
var target = 1000;
var optimum = 0;
var sums = [];
sums.push(optimum);

for(var i=0; i < input.length; i++) {
var newSums = [];
for(var j=0; j < sums.length; j++) {
var newSum = sums[j] + input[i];
if (newSum <= target) {
newSums.push(newSum);
if (newSum > optimum) {
optimum = newSum;
}
} else if ((Math.abs(target-newSum) < Math.abs(target-optimum)) || (Math.abs(target-newSum) == Math.abs(target-optimum) && newSum > optimum)) {
optimum = newSum;
}
}
sums = sums.concat(newSums);
}
return optimum;
}

walrusWeight(input);


Style

You code is not properly indented which makes it quite hard to understand.

Calling your function argument input conveys pretty much as much information as calling it argument. I guess weights or weightList would be more meaningful.

It would probably make sense for target to be a parameter of the walrusWeight function.

Bug

Calling your function with var weights = [4, 900, 500, 498, 4, 1000]; and var target = 1000; gives 1002 as a result.

Tests

Before you try to fix anything, I suggest you write a test suite with your function being called with various inputs and the result you are expecting. This will make the developement of a new solution much easier.

Algorithm

Because your current solution is wrong, you'll need to think about a new algorithm.

A simple, yet, efficient enough with small-ish inputs it to iterate over the weight and keep tracks of the various possible sums :

With [4, 900, 500, 498, 4, 1000], you'd get something like :

1. iteration 0 : possible sums = [0]
2. iteration 1 : possible sums = [0, 4]
3. iteration 2 : possible sums = [0, 4, 900, 904]
4. iteration 3 : possible sums = [0, 4, 900, 904, 500, 504, 1300, 1304]
5. iteration 4 : possible sums = etc
6. iteration 5 : possible sums = etc

When you'll have all candidates, it's easy to pick the best.

Then, you'll find various optimisations (get rid of values that won't need to solution early on) but it's a good idea to make it right and then make it fast.

Code example

I've tried to implement the suggestions above :

var weights = [2000, 1003, 4, 900, 500, 498, 3, 8];
var target = 1000;

function walrusWeight(weights) {
var optimum = 0;
var optimum_distance = target;
var sums = [0];

for(var i=0; i < weights.length; i++) {
var weight = weights[i];
var newSums = [];
for(var j=0; j < sums.length; j++) {
var sum = sums[j];
if (true) // An optimisation could be added here
{
newSums.push(sum)
var newSum = sum + weight;
var distance = Math.abs(target - newSum)
if (newSum <= target)
{
newSums.push(newSum)
if (distance < optimum_distance) {
optimum = newSum;
optimum_distance = distance;
}
}
else if (distance < optimum_distance || (distance == optimum_distance && newSum > optimum))
{
optimum = newSum;
optimum_distance = distance;
newSums.push(newSum)
}
}
}
sums = newSums;
print(sums)
}
return optimum;
}

print(walrusWeight(weights, target));