Unbounded Knapsack!


#1

‘’’
vector Solution::solve(int S, vector &wt) {

int n=wt.size();



vector<int> dp(S+1,-1),back(S+1);

for(int i=0;i<=S;i++){ // in normal unbounded we iterate over every Sum by including item one by one
    
    for(int j=0;j<n;j++){//this order is changed for lexographically minimum
        
        if(i>=wt[j] && dp[i]<dp[i-wt[j]]+1){
            dp[i]=dp[i-wt[j]]+1;
            back[i]=j;
        }
        
    }
}

vector<int> r;
while(S>=0 && S-wt[back[S]]>=0){
    r.push_back(back[S]);
    S-= wt[back[S]];
}



return r;



// return {};

}


#2

hey can u explain this code in detail