动态规划-背包问题——[模版]01背包(背包母题)

1.题目解析

 题目来源

[模版]01背包_牛客题霸_牛客网

 测试用例

2.算法原理

1.状态表示

第一小问：求最大价值

第二小问：求充满时的价值 

2.状态转移方程

第一小问：求最大价值

第二小问：求充满时的价值

3.初始化

第一小问：求最大价值

 

第二小问：求充满时的价值

4.填表顺序

从上到下，每一行从左到右

5.返回值

返回dp[n][V]，第一小问代表在[1,n]个物品取出总体积不大于V的物品的最大总价值

第二小问代表在[1,n]个物品中取出物品体积恰好为V的总价值

3.实战代码

#include <iostream>
#include <string.h>
using namespace std;

const int N = 1010;
int dp[N][N];
int w[N];
int v[N];
int n,V;

int main()
{
    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]);
            }
        }
    }
    cout<<dp[n][V]<<endl;

    memset(dp,0,sizeof(dp));

    for(int j = 1;j <= V;j++)
    {
        dp[0][j] = -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]);
            }
        }
    }
    cout<<(dp[n][V] == -1 ? 0 : dp[n][V])<<endl;

    return 0;
}

代码解析 

4.优化代码(主要针对空间的优化)

#include <iostream>
#include <string.h>
using namespace std;

const int N = 1010;
int dp[N];
int w[N];
int v[N];
int n,V;

int main()
{
    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]);
        }
    }
    cout<<dp[V]<<endl;

    memset(dp,0,sizeof(dp));
    
    for(int j = 1;j <= V;j++)
    {
        dp[j] = -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]);
            }
        }
    }
    cout<<(dp[V] == -1 ? 0 : dp[V])<<endl;

    return 0;
}

优化细节对比  

这里的优化是使用了滚动数组的方法对空间进行优化，当然时间上也有一定的优化

在初始代码我们可以看出当填写dp[i][j]时只用到了dp[i-1][j]与dp[i-1][j-v[i]]这两个位置的值，所以不妨去掉i下标，设置滚动数组只保留这三个位置的值

至于为什么可以去除i下标，因为i下标起的作用就是保证在[1,n]区间取物品，而在循环时就已经保证一定会在这个范围去取物品放入背包，所以不必多此一举

并且注意在填写后面位置需要用到前面滚动数组的值，那么就需要从后向前遍历才能保证前面位置的值在填写后面位置的值时不会被更新，并且将循环条件改为判断j>=v[i]，还可以对时间进行一定的优化

 

原文地址：https://blog.csdn.net/2301_80689220/article/details/143661096

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！