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];
}
}
上一篇: DP - 背包九讲之完全背包
下一篇: 完全背包(DP入门)