[数据结构与算法]动态规划——01背包

题目描述

01背包：给你n个物品，每个物品都有一个体积和价值，且物品只有一个，给你一个背包体积v，要求背包里面装的物品价值之和最大。

问题求解

对于背包问题，我们都能从下面的思路进行思考：
问题中不是有n个个物件嘛，也就是从0到n个物件中找出体积小于v的最大价值。
我们分解问题，我们从0到i中找小于体积j的最大价值，不包括i，因为问题求的就是包括i的最大价值（后文表示：f(i-1，j)）.
而f(i-1,j)是可以求的，怎么求f(i,j)呢？——很简单，去掉第i件物品，那么f(i,j)就可以表示为，f(i-1,j-v[i])+w[i]——v[i]第i件物品的体积 ,w[i]第i件物品的价值。
总结：
最大价值==f(i,j)==f(i-1,j)与f(i-1,j-v[i])+w[i]相比的最大值。

牛客网01背包

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

int main()
{
    int V,N;
    cin>>V>>N;
    vector<int> v(N+1),w(N+1);
    for(int i=1;i<=N;++i)
        cin>>v[i]>>w[i];
    vector<vector<int>> f;
    f.resize(N+1);
    for(auto& x:f)
        x.resize(V+1);
    //上面都多1个是为了更好的表达
    for(int i=1;i<=N;++i)
    {
        for(int j=1;j<=V;++j)
        {
            f[i][j]=f[i-1][j];//把前i-1物品的最大值传递给前i物品
            if(j>=v[i])//说明可能装下这个，如果装的下，他就是最大值，但是不能求出，要进转化
                f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<f[N][V]<<endl;
    return 0;
}

优化：

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

int main()
{
    int V,N;
    cin>>V>>N;
    vector<int> v(N+1),w(N+1);
    for(int i=1;i<=N;++i)
        cin>>v[i]>>w[i];
    vector<int> f;
    f.resize(V+1);
    for(int i=1;i<=N;++i)
    {
        for(int j=V;j>=v[i];--j)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[V]<<endl;
    return 0;
}

优化解释

为什么可以向上面那样优化呢？

• 因为我们发现都选取不同的i的时候，上一层的空间就是被搁置的，没有被利用的，那么为什么我们不能用上一层的空间呢？

下面主要是解释循环体里面的代码；
之前的代码：

        for(int j=1;j<=V;++j)
        {
            f[i][j]=f[i-1][j];//把前i-1物品的最大值传递给前i物品
            if(j>=v[i])//说明可能装下这个，如果装的下，他就是最大值，但是不能求出，要进转化
                f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }

我们把2维缩成1维，即只用原来的一行，该行的j列表示从所有的物品中选取不超过j空间大小的最大价值。**记住： **每次内循环完成的时候，表示从i个物品中选取的结果完成

如果这样修改：错误的

    	for(int j=1;j<=V;++j)
        {
            if(j>=v[i])
                f[j]=max(f[j],f[j-v[i]]+w[i]);//这里等价与f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);但是这个公式可能会改变上一层的最大值。
        }

怎么解决呢？倒着来，这样就不会出现改变上一层数据的情况

        for(int j=V;j>=v[i];--j)//关键是V的问题，才使下面的方程可以进行转换
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);//小括号里面的f[j]，是上一层的，但是可以理解为这一层的，把上一层的最大值给给了这一层，后面的参数是这一层的，需要转换。f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }