DP10 0-1背包問題 0-1 Knapsack Problem @geeksforgeeks

01背包問題的取和不取實際上就是一個機會成本的問題，如果取了某件東西，盡管當前的價值暫時地增加了，但你付出了機會成本。因為如果不取，留下的空間以後說不定可以放更有價值的東西。因此空間和價值總是一對矛盾。我們的目的是要用有限的空間裝入最優價值的東西。

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).

A simple solution is to consider all subsets of items and calculate the total weight and value of all subsets. Consider the only subsets whose total weight is smaller than W. From all such subsets, pick the maximum value subset.

1) Optimal Substructure:
To consider all subsets of items, there can be two cases for every item: (1) the item is included in the optimal subset, (2) not included in the optimal set.
Therefore, the maximum value that can be obtained from n items is max of following two values.
1) Maximum value obtained by n-1 items and W weight (excluding nth item).
2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).

If weight of nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.

2) Overlapping Subproblems
Following is recursive implementation that simply follows the recursive structure mentioned above.

package DP;

public class ZeroOneKnapsack {

	public static void main(String[] args) {
		int[] wt = {10, 20, 30};
		int[] val = {60, 100, 120};
		int cap = 50;
		int n = wt.length;
		System.out.println(knapSackRec(cap, wt, val, n));
		System.out.println(knapSackDP(cap, wt, val, n));
	}
	
	// Returns the maximum value that can be put in a knapsack of capacity cap
	public static int knapSackRec(int cap, int[] wt, int[] val, int n){
		if(n==0 || cap==0){
			return 0;
		}
		
		// If weight of the nth item is more than Knapsack capacity W, then
		// this item cannot be included in the optimal solution
		if(wt[n-1] > cap){
			return knapSackRec(cap, wt, val, n-1);
		}else{		// Return the maximum of two cases:  (1) not included (2) nth item included
			return Math.max(knapSackRec(cap, wt, val, n-1), 
									knapSackRec(cap-wt[n-1], wt, val, n-1) + val[n-1]);
		}
	}
	
	
	public static int knapSackDP(int cap, int[] wt, int[] val, int n){
		int[][] dp = new int[n+1][cap+1];
		
		for(int i=0; i<=n; i++){
			for(int w=0; w<=cap; w++){
				if(i==0 || w==0){
					dp[i][w] = 0;
				}else if(wt[i-1] > w){		// 因為超重了，所以不選
					dp[i][w] = dp[i-1][w];
				}else{	// 挑不選和選之間價值更大一個
					dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w-wt[i-1]]+val[i-1]);
				}
			}
		}
		
		return dp[n][cap];
	}

}