找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

那些经典算法:动态规划二

admin 2019-10-10 08:28 79人围观 C++相关

上一次聊到动态规划的时候,聊的例子比较简单,但是动态规划确实是比较难的算法,比较难以理解。
动态规划其实算是利用空间换时间的算法,思路和带有备忘录的回溯算法比较像,它的核心是定义每步的状态和状态之间如何转移的问题,但是其实上一篇聊动态规划的算法时候的回溯算法,我感觉更像是一种穷举,没看到回到哪里,是穷举了所有可能,然后选择符合条件的那一个,这一篇我们不再以斐波那契数列为例子,以0-1背包为例子来说明动态规划算法。

题目:给你一个背包, 最多可以承受的重量为w,那么给你一组物品,每个物品无法分割,问在背包总重量和总物品数量不超过约定数量的前提下,如何做才能够让背包的总重量最重。

这个可以按照回溯算法,其实我理解的就是遍历来做,具体实例代码如下:

public class Bag
{
// 存储背包中物品总重量的最大值
private int maxW = Integer.MIN_VALUE;
private static int MAX_NUM = 50;
private int [] chose = new int[MAX_NUM];

public void f(int i, int cw, int[] items, int n, int w) {
// cw==w 表示装满了 ;
// i==n 表示已经考察完所有的物品
if (cw == w || i == n) {
if (cw > maxW) {
maxW = cw;
}
return;
}
//这个是不装第i+1个物品,为什么+1 是因为数组从0开始的
//所以第0个算是第一个物品
f(i+1, cw, items, n, w);
//这个如果没有超重,则装第i+1个物品
if (cw + items[i] <= w) {
f(i+1,cw + items[i], items, n, w);
}
}

public static void main(String [] args)
{
int num = 5, capacity = 10;
int [] weight_list = new int[] {2, 2, 6, 5, 4};
Bag b = new Bag();
b.f(0,0,weight_list,num,capacity);
System.out.println("最大可以放物品总重量:"+b.maxW);
}
}

代码中:

cw 表示当前已经装进去的物品的重量和; i 表示考察到哪个物品了;

w 背包重量;items 表示每个物品的重量;n 表示物品个数

关键的代码f函数,里面对每个物品都调用了放进去和不放进去两种可能,整个算法的复杂度为2^n,很高。画下递归树,借鉴课程里面的:



这个图里面的前两个参数标识第几个物品,后面一个参数标识现有背包的重量,通过上面的图示可以看到,有不少节点是重复的比如f(2,2) 是抉择第3个物品是否需要放入到背包中,现有的总重量为2。第几个物品是判断的,背包的现有重量相同,那么后面的所有子状态树其实是重复的,如果可以去掉,就相当于给这个递归树剪枝了,必然可以提升算法的性能。

像上次的备忘录一样,这次也可以采用备忘录的方式来解决。
public class Bag2 {
// 结果放到 maxW 中
private int maxW = Integer.MIN_VALUE;
// 物品重量
private int[] weight = {2, 2, 4, 6, 3};
// 物品个数
private int n = 5;
// 背包承受的最大重量
private int w = 9;

//备忘录
private boolean [][] store = new boolean[5][10];

public void f2(int i,int cw) {
if (cw == w || i == n) {
if (cw > maxW) {
maxW = cw;
}
return;
}
//已经探测过了,这个分支可以忽略了
if (store[i][cw]) {
return;
}
store[i][cw] = true;
//不装第i个物品
f(i+1,cw);
//装第i个物品,这个+不装第i个物品
//就可以涵盖所有情况
if (cw +weight[i] <= w) {
f(i+1,cw+weight[i]);
}
}

public static void main(String[] args) {
Bag2 bg = new Bag2();
bg.f2(0,0);
System.out.println(bg.maxW);
}
}

带上备忘录的回溯算法性能已经不错了。动态规划的思路和这个类似。动态规划将步骤分为n步,每一步来抉择一个物品是放入还是不放入,每个决定都可以看作一种状态,同一层不同状态的个数是不会超过w个,这个是由背包的总承重大小来决定的。

下面的定义就比较难以理解:
定义一个二维数组,states[n][w+1],n标识多少层,比如n为0时候,来标识第一个物品是否放入到背包内,第二维标识现有的背包的重量,假设物品的重量依次为:2, 2, 4, 6, 3
例如:states[0][0] = true 和states[0][2] = true,表示第一个物品不放入背包和第一个背包放入物品的状态。第2个物品重量为2,基于之前的背包状态,在这个物品决策之后,不同的状态就有三个:state[1][0] = true 第2个物品在第一个物品不放入的情况下也不放入的状态。state[1][2] = true 第2个物品在第一个物品不放入的情况下放入的状态或者第一个物品放入,第二个物品不放入状态, 和回溯的备忘录类似,这里面合并了(0+2和2+0)的状态。state[1][4] = true 第1个物品在第一个物品和第二个物品都放入背包的状态。
依次类推,每次考察一个物品,我们考察最后一层,最接近w即背包承受重量就是能够装的最大重量。





代码示例如下:
public class Bag2 {
// 结果放到 maxW 中
private int maxW = Integer.MIN_VALUE;
// 物品重量
private int[] weight = {2, 2, 4, 6, 3};
// 物品个数
private int n = 5;
// 背包承受的最大重量
private int w = 9;

public int stack(int n,int w) {
boolean [][] states = new boolean[n][w+1];
states[0][0] = true;
//防止第一个就超了
if (weight[0] <= w) {
states[0][weight[0]] = true;
}
//从1开始是因为第一个物品的两种状态已经都保存了
for (int i = 1; i < n; i++) {
for (int j = 0; j<= w; ++j) {
//每次从i-1到i需要判断是否存在这个状态
//就是有这个重量的情况,没有这个重量的情况就不需要推导了
if (states[i-1][j]) {
//这步标识直接不装第i个物品了
states[i][j] = states[i-1][j];
}
}
for (int j = 0; j <= w- weight[i]; ++j) {
if (states[i-1][j]) {
//这步标识装第i个物品
states[i][j+weight[i]] = true;
}
}
}
//最后一层,从后面向前,因为后面的值更大
for (int i = w; i>= 0; --i) {
if (states[n-1][i]) {
return i;
}
}
return 0;
}

public static void main(String[] args) {
Bag2 bg = new Bag2();
System.out.println("=================");
System.out.println( bg.stack(5,9));
}
}

这个代码的时间复杂度为O(nw),只是需要申请一个n(w+1)的二维数组,如上一篇一样,同样可以减少空间占用,优化如下:
public class Bag2 {
// 结果放到 maxW 中
private int maxW = Integer.MIN_VALUE;
// 物品重量
private int[] weight = {2, 2, 4, 6, 3};
// 物品个数
private int n = 5;
// 背包承受的最大重量
private int w = 9;

public int stack2( int n, int w) {
// 默认值 false
boolean[] states = new boolean[w+1];
// 第一行的数据要特殊处理
states[0] = true;
if (weight[0] <= w) {
states[weight[0]] = true;
}
// 动态规划
for (int i = 1; i < n; ++i) {
// 把第 i 个物品放入背包
// j>=0 说明w- weight[i]
for (int j = w-weight[i]; j >= 0; --j) {
if (states[j]) {
states[j+weight[i]] = true;
}
}
}
// 输出结果
for (int i = w; i >= 0; --i) {
if (states[i]) {
return i;
}
}
return 0;
}

public static void main(String[] args) {
Bag2 bg = new Bag2();
System.out.println("=================");
System.out.println(bg.stack2(5,9));
}
}

这个有点能以理解,我来说明下,仔细观察上面表格,其实我们关注的只是每次背包中存放的最大数量,至于哪个选中的,这个里面并没有说明,也不用指出。
states[i] 标识 重量为i的这种情况是否存在。
手工演示下:
1) 第一个物品 得到 states[0] = true states[2] = true

2) 第二个物品 j从大到小循环,j = 9 - 2 = 7 循环发现state[2] = true,则添加states[2+weight[1]] = true 即:states[4] = true,这就是考虑第二个放入的情况。发现state[0] = true 则添加:state[0+weight[1]] = true 即states[2] = true 不放入第二个的情况,就是0+0和2+0,2+0这种情况已经隐含在第一个states[2] = true里面了,states[0]也已经为true了。
   现在states[0] = true states[2] = true  states[4] = true。
   和表格上一样的,这里面states[0+0] = true这种为什么没考虑,是因为states[0]已经为true了,以后任何情况都不要考虑前面都不
   选的情况,选一个的情况也被涵盖了。
3) 第三个物品:j = 9 - 4 = 5 ,循环发现stats[4] = true,则states[4+weight[2]] = true 即:states[8] = true。
states[2+4] = true 即states[6] = true。
现在:states[0] ,state[2],state[4],state[6],state[8] 均为true,和图中可以对比下,是一样的。

4) 关于下面代码:
for (int j = w-weight[i]; j >= 0; --j) {
if (states[j]) {
states[j+weight[i]] = true;
}
}

改成:
for (int j = 0; j <= w-weight[i];j++) {
if (states[j]) {
states[j+weight[i]] = true;
}
}

满足if条件的更多,本次计算,第一个循环11次,第二个循环15次。

就聊到这里吧,动态规划内容还没结束,下次接着聊。


----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:啐啐念,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......