动态路径规划——01背包问题讲解和通过滚动数组优化

        如果没有动态路径规划基础的兄弟可以出去了，这个题目有两个问题

        第一问讲解：

        1.定义状态表示

        刚开始我做的时候根据我的经验定义了一个状态表示dp[i]表示从1到i个物品中选择的最大价值，但是这个状态表示有一个明显的问题，我怎么知道第i个物品可不可以放入背包？

        所以这个一维的状态表示显然是不够的，在上面的时候其实我们只需要知道第i个物品能不能放入背包其实状态表示就完全了，故我们用二维的dp[i][j]来进行状态表示，它表示从1到i个物品中选择容积小于等于j的最大价值

        2.状态转移方程的推导

        对于第i个物品我们只有两种选择，要么拿要么不拿

        2.1 当我们不拿时那么我们的dp[i][j]显然和dp[i-1][j]是相等的

        2.2 当我们拿时需要先判断空间够不够，如果空间足够那么

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

        3.初始化

        3.1 当i为0时说明没有物品那么容积小于等于j的最大价值其实就是0

        3.2 当j为0时说明容积为0那么最大价值也是0

        4.填表顺序

        观察状态转移方程，我们发现dp[i][j]j会用到前一行的数据（这里是我们后面优化的关键），所以我们的填表顺序是从上往下、从左往右。

#include<iostream>
 
using namespace std;
 
const int N = 1010;
 
int n,V,v[N],w[N];
int dp[N][N];
 
int main()
{
    int ret1 = 0;
    cin>>n>>V;
    for(int i = 1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=V;j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j>=v[i]) dp[i][j] = max(dp[i][j],
                dp[i-1][j-v[i]]+w[i]);
            ret1 = max(ret1,dp[i][j]);
        }
    cout<<ret1<<endl;
    return 0;
}

        第二问讲解

        1.定义状态表示

        与第一问很像，但是这是并不是容积小于等于j的最大价值而是容积等于j的最大价值

        2.状态转移方程

        和第一问差不多，但是我们需要设定一个值来表示从1到i选不到容积为j的情况这里用-1来表示

        那么对于第i个位置同样有两种情况

        2,1 当我们不拿第i个物品时价值为dp[i-1][j](这里已经将选不到容积为j的情况包括)

        2.2 当我们如果要拿第i个物品时，那么我们首先当然是先判断空间j够不够，然后还要判断

dp[i-1][j-v[i]]这个位置是否有意义即是否为-1，如果有意义那么

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

        3.初始化

        这里当i == 0时如果要选择容积等于j的最大价值显然是没有意义的所以我们将dp[0][j](j>=1&&j<=V)初始化为-1

        当j == 0时只需要不选择物品即可所以初始化dp[i][0]（i >= 1&&i<=n）为0

        4.填表顺序同上

 for(int i = 1;i<=V;i++) dp[0][i] = -1;
    int ret2 = -1;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=V;j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j>=v[i] && (dp[i-1][j-v[i]] != -1))
                dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
        }
    for(int i = 1;i<=n;i++) ret2 = max(ret2,dp[i][V]);
    if(ret2 == -1) cout<<0<<endl;
    else cout<<ret2<<endl;

下面讲讲这个算法的优化

        我们在填表的时候发现只用到了相邻的两行其实这里可以用滚动数组来优化，只需要一个dp[N]即可当我们填表时只需要在原表操作，但是我们的填表顺序变为了从右往左因为在填dp[i][j]时我们用到了dp[i-1][j]和dp[i-1][j-v[i]]显然dp[i-1][j-v[i]]位置在dp[i-1][j]前面所以如果从左往右填表会导致在填后一个位置的时候前面的位置的值已经被更新

#include<iostream>

using namespace std;

const int N = 1010;

int n,V,v[N],w[N];
int dp[N];

int main()
{
    int ret1 = 0;
    cin>>n>>V;
    for(int i = 1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i = 1;i<=n;i++)
        for(int j = V;j>=v[i];j--)
        {
            dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
            ret1 = max(ret1,dp[j]);
        }
    cout<<ret1<<endl;
    //第二问的初始化
    for(int i = 1;i<=V;i++) dp[i] = -1;
    int ret2 = -1;
    for(int i = 1;i<=n;i++)
        for(int j = V;j>=v[i];j--)
        {
            if((dp[j-v[i]] != -1))
                dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
        }
    for(int i = 1;i<=n;i++) ret2 = max(ret2,dp[V]);
    if(ret2 == -1) cout<<0<<endl;
    else cout<<ret2<<endl;
    return 0;
}