0-1 knapsack

• Define a array to record the optimized value : dp[i], i means from item[0] ~ item[1], value means the maximun profits by far

For each item in knapsack:

• Decide if we are able to take that item

• if yes, check the consequnce of taken / not taken

• if no, then it's consequnce is equal to (skip/not take) this item

for(Item item : items){

    if(canWeTake(item)){
        dp[i] = Max(dp[i-1], dp[i-1] + item.value);
    }
    else{
        dp[i] = dp[i-1];
    }
}

Problems related to "Taken" or "Not Taken", can be solved by the below approach.

And with memorization to record the temp results, can optimize the time complexity to O(N*M), N is the item number, M is the initial capacity.

int[][] items;
int max = 0;
public int findOpt(int[][] items, int capacity){
    this.items = items; //[0] : weight, [1] : value
    int n = items.length;
    for(int i = 0; i < n; i++){
       max = Math.max( max, helper(i, capacity));
    }
    return max;
}


public int helper(int itemIndex, int capacity){
    if(canTaken){ //capacity > items[itemIndex][0]
        return Math.max( helper(itemIndex+1, capacity) , items[itemIndex][1] + helper(itemIndex+1, capacity - items[itemIndex][1])
    }
    return helper(itemIndex+1, capacity);
}