算法设计与分析学习笔记：动态规划（2）

#0-1背包问题

##问题描述：

从前有个程序员跑到了森林里，他发现地上有好几块宝石，大小不一，价值各异，我嘞个嚓嚓！发了诶！再也不用加班了有木有！！可惜啊，由于长期编码不锻炼身体，这哥们只能拿得动 c 公斤的东西，那么问题来了，他怎么拿才能赚得最多，买房买车迎娶白富美走上人生巅峰？

##问题分析：

咋拿呢？ 作为一个程序猿， 他无耻的想到了动态规划四个字,为什么用动态规划呢？
先形式化描述：

假设宝石数量n=3，每块的重量分别是 w{6,5,4} 价值分别是 v{15,14,18}，背包容量c为11,求怎么拿能使背包中价值最大？

看到最大有没有想到最优子结构呢？
这个问题，只要智商大于0，都能看出来拿 1,3号宝石，最大的价值为33。

现在假设他已经拿了第3块宝石，那么现在只能拿 c-$w_3$ = 11-4 = 7重量的宝石，于是问题变为c=7,n=2,重量{6,5}价值{5,4}的0-1背包问题，
这就是子问题，显然剩下的两块只能拿一块，显然拿第一块获利最多，即n=2时，他拿的是第1块宝石，这就是传说中的“全局最优解包含局部最优解”。

现在来理一理思路：当n=2时，我们要求的是前2个宝石， 装到体积为7的背包里能达到的最大价值；当n=3时，我们要求的是前3个宝石， 装到体积为11的背包里能达到的最大价值。有没有发现规律！
我们定义：d(i,j)为前i个物品放入容量为c的背包中的最大价值
那么上面的两句话就是 d(2,7) and d(3,11) ，前面说道：动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件。要做到这一点，就必须将原问题分解为几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类的子问题，然后逐个求解。 那么状态是如何转移的呢?
从d(3,11) 怎么转换为d(2,7)　呢？这就涉及到　第３个宝石的放与不放的问题了：如果不装入，那么价值不变　即d(3,11) = d(2,11)，如果放入呢，那么价值就变为　d( 3,11 ) = d( 2 , 10-$w_3$ )+$v_3$
那么决策变量是什么呢？　决策变量就是要求价值是最大的,即
d(3,11) = max{ d(2,11) , d(2, 7)+18}
形式化一下：
d(n,capacity) = max{ d(n-1,capacity) , d( n-1 , capacity-$weight_n$) + $value_n$ }

但是这个递归式不能完整描述所有情况，因为前面的假设是所有单个宝石的重量都比背包的容量小（即都能装入背包），如果有的宝石重量比背包的容量大就不能装了，所以　递归方程要改为:

$$
d(n,capacity) = max(d(n-1,capacity),d(n-1,capacity-weight_n) + value_n), capacity>= w_n
$$

$$
d(n,capacity) = d(n-1,capacity), capacity < w_n
$$

边界条件是什么呢？　对于初始情况，第一个物品有２中选择，放或者不放，
放的话 d(1,capacity) = $v_1$ , 不放的话 d(1,capacity) = 0

那么初始状态方程就是

$$
d(1,capacity) =
\begin{cases}
v_1, & \text{capacity >= w_1}\
0, & \text{capacity < w_1}
\end{cases}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
int max_value(const int n,int capacity,int *value,int *weight,int **max){
    // 先初始化边界条件
    for(int i = 0; i < capacity;++i){
        if(capacity < weight[i]) {
            max[0][i] = 0;
        }else{
            max[0][i] = value[0];
        }
    }
    // 然后从前往后填表
    for(int row = 1; row < n; ++row){
        for( int current_capacity = 0; current_capacity < capacity; ++ current_capacity ){
            if(weight[current_capacity] > current_capacity){
                max[row][current_capacity] = max[row-1][current_capacity];
            }else{
                max[row][current_capacity] = max[row-1][current_capacity] > max[row-1][current_capacity-weight[current_capacity]] + value[current_capacity] ? max[row-1][current_capacity] : max[row-1][current_capacity-weight[current_capacity]];
            }
        }
    }
    return max[n][capacity];
}

Comments

⬆︎TOP