# 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:&#x20;

* Decide if we are able to take that item&#x20;
* if yes,  check the consequnce of taken / not taken
* if no, then it's consequnce is equal to (skip/not take) this item&#x20;

```java
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.&#x20;

```java
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);
}



```
