动态规划01背包

1.引入,动态规划

简单来说动态规划就是找最优解。

举个很简单的例子,小时候我们都做过一个题目:小明要做饭,其中淘米1min,蒸饭10min,洗菜2min,炒菜15min,问做完这一餐饭小明最短需要多少时间?

这就是一个动态规划的问题,我既可以按照顺序,淘米->蒸饭->洗菜->炒菜,这样一步一步做下去,也可以先洗菜,再炒菜,在炒菜的过程中蒸米饭。

总而言之,动态规划问题就是指当问题有很多解决方法的时候(注意可以用动态规划算法来解决的问题,一定是有多种解法其中选择最优解的问题),选择最符合实际的解决方法。

 

 

2.问题,01背包

描述:给定n个物品和一个容量为C的背包,请给出物品装入背包的方案,使得背包中物品的总价值M最大,并满足:

① 每个物品的重量为wi,价值为vi;

② 每个物品不可拆分,要么完整状图背包,要么不在背包里;

③ 背包中物品的总重量不能超过容量C。

那么根据问题来分析,很明显01背包也属于其中动态规划的方法。我要在有限的背包容量中装尽可能价值高的东西,那么装哪些,舍弃哪些就是算法要解决的问题了。

 

 

3.思路,步骤

用动态规划最重要的一个思路就是自底向上。怎么用?简单来说就是,你先把所有的情况全列出来,根据你列出来的规划来找规律。

 

看到这个先来解释一下这个表格各项的意思:C是代表背包可以放下的总重量。我们需要填进去的值是当前情况下背包的总重。如果填到物品2的一行,暗含物品1也是可以填的,物品3不能,以下同。

 动态规划01背包

 

 

 物品1放入背包:

动态规划01背包

可以看到,第一个物品的重量(wi) 2>背包可承载重量(C) 1,所以第一个格子我们的物品1是不能放进去的,重量即为0。而后面的C>wi,所以这时可以理解为,我只有物品1时,且我的背包可以容纳重量为2(3,4,5)的物品时,我的背包可以装的东西最高价值为15。

 

 

 物品1、2放入背包:

动态规划01背包图1

当第二个物品也纳入可选范围时,因为它的wi=1,而且10>0,所以当背包重量为1时,我们的背包价值就可以增加到10(即物品2的价值)。

当我们的背包容量增加到2时,这时,背包里可以放一个物品1,一个物品2,15和10相比,就可以很明显的发现只放一个物品1,价值是相对最大的。

背包容量增加到3,这时就有三个选择了,一个物品1,一个物品2或者干脆两个一起放,那么三个数字一相比较(如图1),可以发现三个物品一起放的价值是最大的(10+25=25)。那么物品2加入后,图表应为:

动态规划01背包

 那么这里我们就可以进行第一个总结:首先要先和上一个格子里的最大价值进行比较,如果比这一列的上一个最大值小,那么就顺理成章的继承。

 

 

 物品1、2、3放入背包:

动态规划01背包

 当背包容量到3的时候,可以是25(物品1+物品2=25)也可以是20(物品3的价值),25>20,所以这里最大容量是25。

 当背包容量到4的时候,可以是25,20,30(物品2+物品3=30),所以这里的最大容量是30。

 当背包容量到5的时候,可以是25,30,35(物品1+物品3=35),所以这里的最大容量是35。

 所以加入了物品3后,最后的表格应该是:

动态规划01背包

 

现在我们的表格已经全部填写完整了,接下来就是找规律。

物品2+物品3 -> array[1][0]=10+物品3的vi

物品1+物品3 -> array[1][1]=15+物品3的vi

那么这里我们就可以进行第二个总结:max(array[x-1][y],array[x-1][y-wi-1]+vi),这里现实比较,再选择大的一个去填入。

但是我们可以看到我们的公式,如果是在第一排或者第一列那减1就溢出了,所以为了方便我们去计算,我们就选择加一列数方便计算。

动态规划01背包

 

 我们的公式就变为了:max(array[x-1][y],array[x-1][y-wi]+vi)

 

4.代码

#include <iostream>
#include <algorithm>
using namespace std;

void DProcessing(int wi, int vi, int m[50][50], int c,int x, int y)
{
    if (wi > c)
        m[x][y] = m[x - 1][y];
    else
        m[x][y] = max( m[x - 1][y], vi + m[x - 1][y - wi] );
}

int main()
{
    int N, n;
    cout << "Please input the weight of the bag:";
    cin >> N;
    cout << "Please input the number of the bag:";
    cin >> n;
    int m[50][50], c[50], wi[50], vi[50];
    for (int i = 0; i < N; i++)
        c[i] = 1 + i;
    cout << "Please input the every bag's wright and value:";
    for (int i = 0; i < n; i++)
        cin >> wi[i] >> vi[i];

    for (int j = 0; j < N + 1; j++)
        m[0][j] = 0;
    for (int i = 0; i < n + 1; i++)
        m[i][0] = 0;

    for (int x = 1; x < n + 1; x++)
        for (int y = 1; y < N + 1; y++)
            DProcessing(wi[x - 1], vi[x - 1], m, c[y - 1], x, y);

    for (int i = 1; i < n + 1; i++)
    {
        for (int j = 1; j < N + 1; j++)
        {
            cout << m[i][j] << " ";
            if (j == N)
                cout << endl;
        }
     }
}
上一篇:魔众企业VI系统 v3.1.0 全新升级,界面优化


下一篇:(VI)事务:Spring 事务-XML配置