DP背包之01背包、完全背包、多重背包笔记

这是个经典话题，值得好好研究一番，本文作为学习笔记将会不断更新。

主要参考了以下资料：

背包问题九讲：http://love-oriented.com/pack/Index.html

背包之01背包、完全背包、多重背包详解 ：http://www.wutianqi.com/?p=539

背包问题九讲笔记_01背包：http://blog.csdn.net/insistgogo/article/details/8579597

背包问题九讲笔记_完全背包：http://blog.csdn.net/insistgogo/article/details/11081025

背包问题九讲笔记_多重背包：http://blog.csdn.net/insistgogo/article/details/11176693

01背包、完全背包、多重背包：http://blog.csdn.net/wzy_1988/article/details/12260343

受益匪浅！

以下是Java的实现：

package DP;

import java.util.Arrays;

public class Knapsack01 {

	static int N = 3;	// 物品个数
	static int V = 5;	//背包最大容量  
	static int[] weight = {0,3,2,2};	//物品重量  
	static int[] value = {0,5,10,20}; //物品价值
	static int[][] dp1 = new int[N+1][V+1];
	
	public static void main(String[] args) {
		System.out.println(knapsack01_2D());
		System.out.println(knapsack01_1D());
		System.out.println(completeKnapsack());
		System.out.println(multiKnapsack());
	}
	
	/* 
	01背包
	目标：在不超过背包容量的情况下，最多能获得多少价值 
	 
	子问题状态:f[i][j]:表示前i件物品放入容量为j的背包得到的最大价值 
	 
	状态转移方程:f[i][j] = max{f[i - 1][j],f[i - 1][j - weight[i]] + value[i]} 
	 
	初始化:f数组全设置为0 
	*/  
	public static int knapsack01_2D(){
		//递推  
		for(int i=1; i<=N; i++){		 //枚举物品 
			for(int j=0; j<=V; j++){		//枚举背包容量
				dp1[i][j] = dp1[i-1][j];
				if(j >= weight[i]){
					dp1[i][j] = Math.max(dp1[i-1][j], dp1[i-1][j-weight[i]]+value[i]);
				}
			}
		}
		return dp1[N][V];
	}
	
	
	//===============================
	static int[] dp2 = new int[V+1];
	/* 
	目标：在不超过背包容量的情况下，最多能获得多少价值 
	 
	子问题状态:f[j]:表示前i件物品放入容量为j的背包得到的最大价值 
	 
	状态转移方程:f[j] = max{f[j],f[j - weight[i]] + value[i]} 
	 
	初始化:f数组全设置为0 
	*/  
	public static int knapsack01_1D(){
		for(int i=1; i<=N; i++){			//枚举物品    
			for(int j=V; j>=weight[i]; j--){	//注意要逆序枚举容量!!! 防越界，j下限为 weight[i]
				dp2[j] = Math.max(dp2[j], dp2[j-weight[i]]+value[i]);
			}
			System.out.println(Arrays.toString(dp2));
		}
		return dp2[V];
	}

	
	
	/* 
	完全背包
	f[i][v]:前i件物品放入背包容量为v的背包获得的最大收益 
	 
	f[i][v] = max(f[i - 1][v],f[i - 1][v - k * Wi] + k * Vi,其中 1<=k<= v/Wi) 
	 
	边界条件 
	f[0][v] = 0; 
	f[i][0] = 0; 
	
	总的复杂度为O(NV*Σ(V/c[i]))
	*/ 
	static int[][] dp3 = new int[N+1][V+1];
	public static int completeKnapsack(){
		
		for(int i=0; i<=N; i++){
			dp3[i][0] = 0;
		}
		for(int v=0; v<=V; v++){
			dp3[0][v] = 0;
		}
		for(int i=1; i<=N; i++){
			for(int v=1; v<=V; v++){
				dp3[i][v] = 0;
				int nCount = v / weight[i];
				for(int k=0; k<=nCount; k++){
					dp3[i][v] = Math.max(dp3[i][v], dp3[i-1][v-k*weight[i]]+k*value[i]);
				}
			}
		}
		return dp3[N][V];
	}
	
	
	//=====================================
	/* 
	多重背包
	f[i][v]:表示把前i件物品放入容量为v的背包中获得的最大收益。 
	f[i][v] = max(f[i - 1][v],f[i - 1][v - k * Weight[i]] + K * Value[i]);
	其中1 <= k <= min(Num[i],V/Weight[i]) 注意这里受到Num[i]的约束  
	//初始化 
	f[i][0] = 0; 
	f[0][v] = 0; 
	*/
	static int[] num = {0,10,5,2};	//物品数量
	static int[][] dp4 = new int[N+1][V+1];
	public static int multiKnapsack(){
		int nCount = 0;
		for(int i=0; i<=N; i++){
			dp4[i][0] = 0;
		}
		for(int v=0; v<=V; v++){
			dp4[0][v] = 0;
		}
		
		for(int i=1; i<=N; i++){
			for(int v=1; v<=V; v++){
				dp4[i][v] = 0;
				nCount = Math.min(num[i], v/weight[i]);
				for(int k=0; k<=nCount; k++){
					dp4[i][v] = Math.max(dp4[i][4], dp4[i-1][v-k*weight[i]]+k*value[i]);
				}
			}
		}
		return dp4[N][V];
	}
}