这是个经典话题,值得好好研究一番,本文作为学习笔记将会不断更新。
主要参考了以下资料:
背包问题九讲: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 acm 背包 dp 背包讲解 动态规划优化 斜率优化
acm algorithm dp 背包9讲 acm algorithm dp 背包9讲acm algorithm dp 背包9讲acm algorithm dp 背包9讲acm algorithm dp 背包9讲
多重背包单调队列优化问题.pdf
DP 背包问题详解pdf
DP算法篇之初学背包问题 DP算法篇之初学背包问题 DP算法篇之初学背包问题
完全背包问题,0-1背包问题,多重背包......
动态规划(DP)——背包问题算法详解[背包九讲]
《背包问题九讲》,dd_engi大神...目录:1、01背包问题;2、完全背包问题;3、多重背包问题;4、混合三种背包问题;5、二维费用背包问题;6、分组的背包问题;7、有依赖的背包问题;8、泛化物品;9、背包问题的变化;
关于dp(动态规划)中的背包问题的讨论,还有很多总结,这上面是用思路引导我们去慢慢理解背包问题的
内含57份dp 背包的专项练习题目,是一个大牛整理的,对于学习信息学的oier是十分的经典。 全部有测试数据和标程。
背包之01背包、完全背包、多重背包详解 Dynamic+Programming 典型的动态规划,用递归下的记忆化搜索来实现 1088 POJ 动态规划加速原理之四边形不等式 基于连通性状态压缩的动态规划问题 对一些DP题目的小结 树型动态...
学过算法的应该都知道动态规划里有个特例 就是背包算法 这里的文档能提供你几乎常见于不常见的应用背包的例子 很详细哦
动态规划01背包
0-1背包问题,部分背包问题。分别实现0-1背包的DP算法,部分背包的贪心算法和DP算法。附件中包含所有算法源代码.c文件,修改下文件名直接编译执行即可
背包DP与树形DP从零起步,形象讲解让你更了解DP
背包九讲: P01:01背包问题 P02:完全背包问题 P03:多重背包问题 P04:混合三种背包问题 P05:二维费用的背包问题 P06:分组的背包问题 P07:有依赖的背包问题 P08:泛化物品 P09:背包问题问法的变化
背包九讲·经典DP~一个牛人发的背包九讲。。。从那里转过来的
在中国,背包问题一般是这样描述的:设n个重量为(W1,W2,...Wn)的物品和一个载重为S的背包,将物品的一部分xi放进背包中的利润是Pixi,问...问能否从这n件物品中选择若干件放入此背包,使得放入的重量之和正好为S。
楼天城牛关于队列优化多重背包,经典的经典
因此,可以选择一个物品的一部分放入背包,而不必完全放入或完全不放入。 背包问题通常可以通过动态规划、贪心算法或者回溯算法来解决。下面是一个简单的动态规划解法的伪代码示例,用于解决0-1背包问题: ```...