01背包

        有一个空间为V的包和一些重量为w[i], 体积为v[i]的物品，选择其中一些物品装到包里，使得装的重量最重，物品只能选择拿或者不拿，不能拿一部分，这类问题称为01背包问题。

        解决这类问题的笨办法就是排列组合，把所有可能的组合列出来，然后在结果中选择体积相加小于等于V的，且重量最重的方案。

        这章主要使用动态规划的方案来解决背包问题，由题目可知，选择第n件物品后，并不会影响前n-1件物品的重量，因此可以使用动态规划的方法来处理，且其状态转移方程为：

Max[i][V] = MAX{Max[i-1][V], Max[i-1][V-v[i]]+w[i]} //其中V是最大价值 Max[][]为I个物品的最大价值

        题：以下物品，选择其中一些放入最大承重为10的包中，最大能装多少价值的商品？

image.png

        分析：01背包问题可以通过列表格处理，假设只有手机，那么不管怎么拿，当包可以承受2以上的重量时，最大的价值都是1500, Max为有N件物品背包W重时的最大价值，则Max[1][1]=0, 其余Max[1][2-10]=1500

image.png

        接着加入手表，则重量1的时候则是放手表价值最大（3000），2的时候也是手表（相当于只有手机一件物品的时候最大价值Max[1][2]=1500，当可以选手机时，Max[1][2]的最大价值就编变成了3000，因为体积Max[1][2-1]+3000 > Max[1][2]）=>0+3000>1500，，因此表格变成如下：

image.png

        第3格=MAX{Max[1][3], Max[1][2]+3000}=MAX{1500,1500+3000}=4500,这跟上一步的推理方法一致。然后再加入电脑，表格变成如下：

image.png

        当加入电脑，重量为5的时候，为什么不是2500，而是4500呢，因为之前拿手表和手机就已经可以达到4500的价值，所以重量5的时候拿了手机和手表就放不下电脑了，因此最大还是4500，当重量为6的时候，可以放下手表和电脑，也就是Max[2][6-5]+2500=5500，大于Max[2][6]的4500，因此Max[3][6]=5500, 同理Max[3][8]=7000。通过进一步更新，最后可以得到如下表格，最大价值也就是最后的13000.

image.png

#include <iostream>
using namespace std;

int value[7][2]={{0,0},{2,1500},{1,3000},{5,2500},{2,2000},{3,1500},{1,5000}};
int Max[7][10]={0}; //记录最大价值

int main() {
    for (int i = 1; i <= 6; i++)
    {
        for (int j = 1; j <= 10; j++)
        {   
            //当前物品重量比可用的还大，使用原来的
            if (j < value[i][0]) {
                Max[i][j] = Max[i-1][j];
                continue;
            }

            //如果放入当前物品价值可以更大，则记录当前状态的最大价值
            int NewValue = Max[i-1][j-value[i][0]]+value[i][1];
            if (NewValue > Max[i-1][j])  
                Max[i][j] = NewValue;
            else
                Max[i][j] = Max[i-1][j];
        }
    }
    cout << Max[6][10] << endl;
    return 0;
}
//输出
13000

完全背包

        完全背包跟01背包不一样的地方就是，完全背包的物品是无限多的，可以一直拿，但是它们的解法是一样的，如下图，还是以列表格的形式进行求解，，只是初始化的时候不同，完全背包在只有手机的时候，随着包裹的增大，价值也会越来越大。

image.png

        代码如下：在01背包中，并没有进行初始化，因为可以从0开始, ，而完全背包需要先初始化第一行，初始化第一行会使问题简化

#include <iostream>
using namespace std;

int value[4][2]={{0,0}, {2,2000},{3,3000},{1,500}};
int Max[4][11]={0}; //记录最大价值

int main() {
    //先进行初始化表格的第一行
    for (int j = 0; j < 11; j++) 
        Max[1][j] = j/value[1][0]*2000;
    
    //后面和01背包一样
    for (int i = 2; i <= 3; i++) //第1件物品开始
    {
        for (int j = 0; j < 11; j++) //背包0-10
        {   
            //当前物品重量比可用的还大，使用原来的
            if (j < value[i][0]) {
                Max[i][j] = Max[i-1][j];
                continue;
            }

            //如果放入当前物品价值可以更大，则记录当前状态的最大价值
            int NewValue = Max[i-1][j-value[i][0]]+value[i][1];
            if (NewValue > Max[i-1][j])  
                Max[i][j] = NewValue;
            else
                Max[i][j] = Max[i-1][j];
        }
    }
    cout << Max[3][10] << endl;
    return 0;
}
//输出
10000

多重背包

        多重背包问题跟01背包问题的区别是：每种物品的数量不是唯一的，也不是无限的，而是有限的。多重背包的一种常规解法是 ：假设Max[i] 是背包i的情况下的最大价值，则： Max[i] = MAX{Max[i], Max[i]-k*v[i]]+k*w[i]}，也就是说需要多加一个循环来让取第i件物品的时候限定只能取0-K件，然后再根据01背包的解法来解题，这里注意使用反向的方式来解，只需要使用一维数组就可以记录最大价值

image.png

#include <iostream>
using namespace std;

int value[4][3]={{0,0,0}, {2,3000,2},{3,2000,1},{1,500,5}};
int Max[11]={0}; //记录最大价值

int main() {

    for (int i = 1; i <=3; i++)
    {
        for (int j = 10; j >= 0; j--) //注意这里要反过来
        {
            for (int k = 1; k <= value[i][2]; k++)  //选择1-K件
            {
                //当前物品重量比可用的还大，使用原来的
                if (j < k*value[i][0]) {
                    break;
                }

                //如果放入当前物品价值可以更大，则记录当前状态的最大价值
                int NewValue = Max[j-k*value[i][0]]+k*value[i][1];
                if (NewValue > Max[j])  
                    Max[j] = NewValue;
            }
        }
    }
    cout << Max[10] << endl;
    return 0;
}
//输出
9500

        对于多重背包，有一种简化的处理方式，就是把不同数量的物品看成是不同的物品，比如一个手机是物品1，两个手机则是物品2，那么就可以把多重背包问题转化成0、1背包问题。仅仅这样虽然可以减少循环嵌套，但还不能减少计算规模。因此想如下的办法：

        先把物品拆分成2的次幂的相加形式，比如7个文具就是 2^0+2^1+2^2，相当于把7个文具看出3样物品，为什么可以这样，因为1，2，4任意组合可以代替1-7，因此可以使用1，2，4来代替1-7的选择， 如果物品数量不能刚好拆分，则余下的数量归为一类，比如10个文具，就是1+2+4+3，因此只要在初始化的时候对每个物品进行拆分就可以，代码如下：

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

int value[3][3]={{2,3000,2},{3,2000,1},{1,500,5}};
int maxval[100][100] = {0};

int main(){
    vector<pair<int, int>> vecValue;
    //东西转换成0、1背包
    for (int i = 0; i < 3; i++)
    {
        int v = value[i][2]; //总数量
        int k = 1; // 分的数量 1，2，4，8
        while (k) {
            if (v <= k)
            {
                vecValue.push_back(make_pair(value[i][0]*v, value[i][1]*v)); //重量，价值
                break;
            }
            vecValue.push_back(make_pair(value[i][0]*k, value[i][1]*k));
            v -= k;  //分走
            k *= 2;  //下一个部分
        } 
    }
    //此时 vecValue 是新的价值列表, 初始化第一行
    for (int i = 1; i < 11; i++){
        if (i >= vecValue[0].first)
            maxval[0][i] = vecValue[0].second;
    }

    for (int i = 1; i < vecValue.size(); i++)
    {
        for (int j = 1; j < 11; j++)
        {
            //当前物品重量比可用的还大，使用原来的
            if (j < vecValue[i].first) {
                maxval[i][j] = maxval[i-1][j];
                continue;
            }

            //如果放入当前物品价值可以更大，则记录当前状态的最大价值
            int NewValue = maxval[i-1][j-vecValue[i].first]+vecValue[i].second;
            if (NewValue > maxval[i-1][j])  
                maxval[i][j] = NewValue;
            else
                maxval[i][j] = maxval[i-1][j];
        }    
    }
    cout << maxval[vecValue.size()-1][10] << endl;
    return 0;
}
//输出
9500


显示更多
Copyright © 2018-2023 lazypos.cn