欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-12 09:30:48
...

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

主要参考了以下资料:

背包问题九讲: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];
	}
}