Question

Can you please solve this using recursion/ dynamic programming? Any programming language is fine.

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.

Sample Input 1	Sample Output 1
4 900 500 498 4	1002

Sample Input 2	Sample Output 2
1 1	1

Answer 1

Solution :

Following is the dynamic programming approach to the problem.

Language is C++. I have written comments to explain it.

#include <bits/stdc++.h>
using namespace std;

//Weight Wallace has to lift
const int V = 1000;
//boolean array to check if Wallace can lift certain sum of weight
bool can[2*V+1];

int main() {
    int n, x;
    cin>>n;
    can[0] = 1;
    int dist = V, ans = 0;
    for (int i = 0; i < n; ++i) {
        cin>>x;
        for (int j = 2 * V - x; j >= 0; --j) {
            if (can[j]) {
                can[j + x] = 1;
                //if new weight is closer to V, update the ans
                if (abs(j + x - V) < dist) {
                    dist = abs(j + x - V);
                    ans = j + x;
                }
                //if value is equally closer, take the larger one
                else if (abs(j + x - V) == dist) {
                    ans = max(ans, j + x);
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

Code demo :

Input 1 :

Output 1 :

Input 2 :

Output 2 :