Given an array of integers, find the subset sum closest to K

Question

I know this is a knapsack problem where the weights and values are equal but I think I am making a mistake in my coding logic, since its taking too long to complete even for a problem where the number of elements in array (N) is 50 and the maximum sum required (M) 4500.

Just to clarify the question, we are given an array of N positive integers and a positive integer M. The array elements can be used only once. We have to find a subset of this array (not necessarily contiguous) such that the sum is the closest to M but doesn't exceed it.

Here is my attempt using dynamic programming:

int M, N, price[100];
int memo[5000][100];

int dp(int left, int g)
{
    if (left < 0)
        return -10000000;

    if (g == N)
        return M - left;

    if (memo[left][g] != -1)
        return memo[left][g];

    int ans = -1;

    ans = max(ans, dp(left - price[g], g + 1));
    ans = max(ans, dp(left, g + 1));
    //cout<<g<<ln;
    return memo[left][g] = ans;
}

void solve()
{

    cin >> M >> N;

    forn(i, N)
    {
        cin >> price[i];
    }
    int score;
    memset(memo, -1, sizeof memo);
    score = dp(M, 0);
    //print_dp(M,0);

    if (score < 0)
        cout << "NO SOLUTION";
    else
        cout << score << ln;
}

int main(){
    solve();
    return 0;
}

So is there any optimization possible in my code that could help bring me down the complexity because this isn't even the biggest test case, there is a test case with M = 10^9. And also how do I track the actual subset incase of a solution since here I am just returning the final maximum possible sum. Any guidance would be appreciated! Thank you

MBo MBo · Accepted Answer · 2021-02-20T10:26:32

Consider the next code (ideone).

For every price (p) it checks all cells of memo array and marks cell j if it possible to compose value j with p and some previous sum j-p. It also updates jmax - max possible sum and returns it as result. For data set M=9 N=4 {2 3 5 11} it gives 8 as possible sum (<=9) of array items.

#include <iostream>
#include <cstring>
using namespace std;
int M, N, p;
int memo[5000];

int solve()
{

    cin >> M >> N;
    int i, j, jmax = 0;

    memset(memo, 0, sizeof(memo));
    memo[0] = 1;
    for(i = 0; i < N; i++) {
        cin >> p;
        for(j=M; j>=p; j--){
            if(memo[j-p]) {
               memo[j]=1;
               if(j>jmax)
                 jmax = j;
            }
        }
    }
    return jmax;
}

int main(){
    std::cout<<solve();
    return 0;
}

Given an array of integers, find the subset sum closest to K

1 Answers