问题描述

给定一组物品, 每种物品都有自己的重量和价格, 在限定的总重量内, 我们如何选择, 才能使得物品的总价格最高
每种物品只有一件, 要么放进背包, 要么不放, 即只能选择 0 / 1个, 该问题称为0-1背包

解题思路

设 F(i, j)表示放进前 i 种物品, 总容量不超过 j
那么首先可以推出边界条件是:

边界条件 
    if (i == 0) 
        F(0, j) = 0
    if (j == 0) 
        F(i, 0) = 0
    if (w[1] >= j) //如果第一个重量不超过j
        F(1, j) = v[1]	//价值为第一个物品的价值
    else    
        F(1, j) = 0	//超过了肯定就放不进去了

状态转移方程

F(i, j) = max(F(i - 1, j), F(i - 1, j - w[i]) + v[i])

不将第 i 种物品放进背包

如果第 i 种物品不拿,之前的背包容量从j - w[i - 1]增大到 j, 第 i 种不拿只拿到第 i - 1种, 所以是F(i - 1, j), 相当于容量增大到 j, 放东西的选择种类只到第 i - 1 种物品

将第 i 种物品放进背包

如果第 i 种物品拿, 每种物品只能放一次, 所以就是之前容量是 j - w[i] 时的价值 :F(i - 1, j - w[i])再加上第 i 种物品的价值

然后在这两种情况里选择较大值

优化空间复杂度

根据上面给出的状态转移方程我们就可以写出一个二维数组的推导方法来计算最大值, 但是当样例数据增大, 我们要开二维数组的话显然不现实, 所以我们需要优化空间复杂度

假设下图表示一个二维数组 F[i, j]

我们发现, 当我们想要求二维数组中F(i, j)的值的时候, 根据状态转移方程, 我们需要的是上图中标示出的那两个值, 也就是说, 我们其实求出一个值的时候完全可以将存储进它正上方的那个位置, 这样我们只需要用一个一维数组就可以求出所有值

注意, 这时我们必须要从右向左求, 因为要保证替换掉的是之后不会再用到的元素

代码实现


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

int mostValue_01(vector<int>& val, vector<int>& wt, int capacity) 
{
    vector<int> ret(capacity + 1, 0);
    int len = val.size();

    for (int i = 1; i <= len; i++) //控制循环次数
    {
        for (int j = capacity; j >= 1; j--) //从右向左遍历
        {
            if (j >= wt[i]) //可以装下第i种物品
                ret[j] = max(ret[j], ret[j - wt[i]] + val[i]);
        }
    }

    return ret[capacity];
}

int main() 
{
    vector<int> value_{-1,2,3,1,4,6,5};
    vector<int> weight_{-1,5,6,5,1,19,7};
    int capacity = 10;

    cout << "最大价值为 = " << mostValue_01(value_, weight_, capacity) << endl;
}

DP : 0-1背包问题

文章目录