int knapsackRec(int c,int n){//top down
    if(c==0 or n==0){
      return dp[c][n]=0;
    }
    if(dp[c][n]!=-1)return dp[c][n];

    int taken=0;

    int nottaken=0+knapsackRec(c,n-1);
    if(c>=weight[n-1]){
        taken=value[n-1]+knapsackRec(c-weight[n-1],n-1);
    }
    return dp[c][n]=max(taken,nottaken);
}

int knapsackIte(int c,int n){//bottom up
    for(int i=1;i<=n;i++){
        for(int cap=0;cap<=c;cap++){
            int nottaken=dp[cap][i-1];
            int taken=0;
            if(cap>=weight[cap-1]){
                taken=value[i-1]+dp[cap-weight[i-1]][i-1];
            }
            dp[i][cap]=max(taken,nottaken);
        }
    }
    return dp[c][n];
}
int rodR(int rl,int ind){ // Top down
    if(ind==1){
        return rl*price[ind];
    }
    if(dp[rl][ind]!=-1)return dp[rl][ind];

    int nottaken=0+rodR(rl,ind-1);
    int taken=0;
    if(rl>=length[ind]){
        taken=price[ind]+rodR(rl-length[ind],ind);
    }
    return dp[rl][ind]=max(nottaken,taken);
}
void rodIta(int rl){
    vector<int>dp(rl+1,0);
    vector<int>ptable(rl+1,0);
    for(int i=1;i<=rl;i++){
        int mvalue=0;
        for(int j=1;j<=i;j++){
            int taken=price[j]+dp[i-j];
            mvalue=max(mvalue,taken);
        }
        dp[i]=mvalue;
    }
    cout<<dp[rl]<<endl;
    deb(dp);
}
int main(){
    int w=c;
    int i=n;
    while(w>0 and i>0){
        if(dp[w][i]==dp[w][i-1]){
            cout<<"Item "<<i-1<<" wasnt taken\n";
            i--;
        }
        else{
            cout<<"Item "<<i-1<<" was taken\n";
            w-=weight[i-1];
            i--;
        }
    }
}