0-1背包问题概念
背包问题本质是个求最优解的问题：有个背包有V大小的空间可以存放物品，现在有n个物品，每个物品体积分别为v1、v2...、vn，价值分别为w1、w2...、wn。现在求解：如何使物品尽可能多的放在背包中，使得背包中的物品总价值最大？
0-1背包问题指的是每个物品只能使用一次
解决这类问题，大致有2类方法：递归算法、动态规划算法，下面详细讲解3种算法（借鉴了博主的论文）。
一、递归算法
递归算法解决这类问题大致的核心思想：
我们用B[k][C]表示前k个物品放进容量为C的背包里，得到的最大的价值。
我们用自顶向下的角度来看，假如我们已经进行到了最后一步（即求解将k个物品放到背包里获得的最大价值），此时我们便有两种选择：
1、不放第k个物品，此时总价值为B[k−1][C]
2、放置第k个物品，此时总价值为wk+B[k−1][C−vk]
两种选择中总价值最大的方案就是我们的最终方案，递推式（有时也称之为状态转移方程）如下
B[k][C]=max(B[k-1][C],wk+B[k−1][C−wk])
编程如下：
public class test {
//物品总量，最大承重
static int N = 6;
static int W = 21;
static int[][] B = new int[N][W];
static String[][] B_ = new String[N][W];
static int w []=new int[]{0,2,3,4,5,9};
static int v []=new int[]{0,3,4,5,8,10};
static Set<Integer> set = new HashSet<Integer>();//记录最优解(这个解可能包含其他没用的解，需要借助list_delete来删除)
static List<Integer> list_delete = new ArrayList<Integer>();//记录不装入背包的物品
/**
* 时间代价是n
* @param k
* @param C
* @return
*/
public static int knapsack1(int k,int C) {
if(k==0||C==0) {
return B[k][C];
}
if(w[k]>C) {
B[k][C]=knapsack1(k-1,C);
list_delete.add(k);
set.remove(k);
}else {
int value1=knapsack1(k-1,C-w[k])+v[k];//装上了：k-1时的最优解+最后装上的价值=最优价值
int value2=knapsack1(k-1,C);//没装上
if(value1>value2) {
set.add(k);
B[k][C]=value1;
}else {
list_delete.add(k);
set.remove(k);
B[k][C]=value2;
}
}
System.out.println("B["+k+"]["+C+"]的价值是"+B[k][C]);
return B[k][C];
}
public static void main(String[] args) {
// TODO Auto-generated method stub
// knapsack1(5,20);
System.out.println("B["+5+"]["+20+"]的价值是"+knapsack1(5,20));
for (Integer integer :list_delete) {
set.remove(integer);
}
System.out.println(set.toString());
knapsack2();
}
}
该算法的时间复杂度为N。
但是上述的算法还是存在一个问题，自顶向下的思想可能导致计算重复，为此借鉴了博主的论文后，我新加入记忆化搜索（将已经计算好的结果存起来，用到的时候，直接拿来，避免了重复计算）。代码结果如下：
public class test {
//物品总量，最大承重
static int N = 6;
static int W = 21;
static int[][] B = new int[N][W];
static String[][] B_ = new String[N][W];
static int w []=new int[]{0,2,3,4,5,9};
static int v []=new int[]{0,3,4,5,8,10};
static Set<Integer> set = new HashSet<Integer>();//记录最优解(这个解可能包含其他没用的解，需要借助list_delete来删除)
static List<Integer> list_delete = new ArrayList<Integer>();//记录不装入背包的物品
static int[][] memo = new int[N][W+1];//记忆化搜索
/**
* 时间代价是n
* @param k
* @param C
* @return
*/
public static int knapsack1(int k,int C) {
if(k==0||C==0) {
return B[k][C];
}
//如果此子问题已经求解过，则直接返回上次求解的结果
if (memo[k][C] != 0) {
return memo[k][C];
}
if(w[k]>C) {
B[k][C]=knapsack1(k-1,C);
list_delete.add(k);
set.remove(k);
}else {
int value1=knapsack1(k-1,C-w[k])+v[k];//装上了：k-1时的最优解+最后装上的价值=最优价值
int value2=knapsack1(k-1,C);//没装上
if(value1>value2) {
set.add(k);
B[k][C]=value1;
}else {
list_delete.add(k);
set.remove(k);
B[k][C]=value2;
}
}
//添加子问题的解，便于下次直接使用
memo[k][C] = B[k][C];
System.out.println("B["+k+"]["+C+"]的价值是"+B[k][C]);
return B[k][C];
}
public static void main(String[] args) {
// TODO Auto-generated method stub
// knapsack1(5,20);
System.out.println("B["+5+"]["+20+"]的价值是"+knapsack1(5,20));
for (Integer integer :list_delete) {
set.remove(integer);
}
System.out.println(set.toString());
// knapsack2();
}
}
二、动态规划算法
/**
* 时间代价是N*W
*/
public static void knapsack() {
//物品总量，最大承重
int N = 6;
int W = 21;
int[][] B = new int[N][W];
String[][] B_ = new String[N][W];
int w []=new int[]{0,2,3,4,5,9};
int v []=new int[] {0,3,4,5,8,10};
//第k件物品、当前背包容量
int k,C;
for(k=1;k<N;k++) {
for(C=1;C<W;C++) {
if(w[k]>C) {
B_[k][C] = B_[k-1][C]==null?"":B_[k-1][C];
B[k][C]=B[k-1][C];
}else {
int value1=B[k-1][C-w[k]]+v[k];//装上了：k-1时的最优解+最后装上的价值=最优价值
int value2=B[k-1][C];//没装上
if(value1>value2) {
B_[k][C] = (B_[k-1][C-w[k]]==null?"":B_[k-1][C-w[k]])+""+k;
B[k][C]=value1;
}else {
B_[k][C] = B_[k-1][C]==null?"":B_[k-1][C];
B[k][C]=value2;
}
}
System.out.println("B["+k+"]["+C+"]的价值是"+B[k][C]+"；选中的物品是:"+B_[k][C]);
}
}
}
空间复杂度的优化
上面的动态规划算法使用了O(n*C)的空间复杂度（因为我们使用了二维数组来记录子问题的解），其实我们完全可以只使用一维数组来存放结果，但同时我们需要注意的是，为了防止计算结果被覆盖，我们必须从后向前分别进行计算。
我们仍然假设背包空间为5，根据
F(i,C)=max(F(i−1,C),v(i)+F(i−1,C−w(i)))
我们可以知道，当我们利用一维数组进行记忆化的时候，我们只需要使用到当前位置的值和该位置之前的值，举个例子
假设我们要计算F(i,4),我们需要用到的值为F(i−1,4)和F(i−1,4−w(i))，因此为了防止结果被覆盖，我们需要从后向前依次计算结果
最终的动态规划代码如下
/**
* 一维
*/
public static void knapsack2() {
//物品总量，最大承重
int N = 6;
int W = 21;
int[] B = new int[22];
String[][] B_ = new String[N][W];
int w []=new int[]{0,2,3,4,5,9};
int v []=new int[] {0,3,4,5,8,10};
// int w []=new int[]{2,3,4,5,9};
// int v []=new int[] {3,4,5,8,10};
//第k件物品、当前背包容量
int k,C;
for(k=1;k<N;k++) {
for(C=W;C>=w[k];C--) {
int value1=B[C-w[k]]+v[k];//装上了：k-1时的最优解+最后装上的价值=最优价值
int value2=B[C];//没装上
if(value1>value2) {
// B_[k][C] = (B_[k-1][C-w[k]]==null?"":B_[k-1][C-w[k]])+""+k;
B[C]=value1;
}else {
// B_[k][C] = B_[k-1][C]==null?"":B_[k-1][C];
B[C]=value2;
}
}
// System.out.println("B["+k+"]["+C+"]的价值是"+B[C]);
}
System.out.println("B["+W+"]的价值是"+B[21]);
}
————————————————
版权声明：本文为CSDN博主「程序员110」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wangjiaee/article/details/103991188
网友评论