Maximum Sum of K Positive Numbers from N Stacks

Problem

There are n number of stacks of positive numbers are given. The task is to take k numbers from the stacks, so that the summation of the taken numbers is maximized.

• From a stack, only the top item can be taken. After removing the top item, the next item get to the top.

Solution

• Traverse the stacks from left or right.
• Take as much numbers as we want or allowed (posibly zero) from that stack and move forward, don't come back.
• Keep the maximum value at each state.
• Memorize to avoid recalculation.

Code

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

int dp[1010][2010]; //memorization
int n; // will keep the number of stacks
vector<vector<int>>stacks; // stacks

void init(){
    for(int i=0;i<10101;i++){
        for(int j=0;j<2010;j++)dp[i][j]=-1;
    }
}

int ctDP(int idx, int k){
    if(idx>=n||k<=0)return 0;
    if(dp[idx][k]!=-1)return dp[idx][k];
    int m=stacks[idx].size();
    int sum=0;
    for(int i=0;i<=min(m,k);i++){
        if(i!=0)sum+=stacks[idx][i-1];
        dp[idx][k]=max(dp[idx][k],sum+ctDP(idx+1,k-i));
    }
    return dp[idx][k];
}

int main(){
    //load_input(); //load stacks
    n = stacks.size();
    init();
    int ans=ctDP(0,k);
    cout<<ans<<endl;
    return 0;
}

Happy coding!