【OJ】动规练习七之【模板】01背包

zxctscl

发布于 2024-04-10 09:16:32

810

发布于 2024-04-10 09:16:32

文章被收录于专栏：zxctscl个人专栏zxctscl个人专栏

DP41 【模板】01背包

1. DP41 【模板】01背包
2. 分析
3. 代码
4. 优化
5. 优化后代码

1. DP41 【模板】01背包

2. 分析

一、题目解析：来看一下例1，3代表有三个物品，5代表能够容纳的体积。第一行要求中并没有说把背包全部装满，选择价值最大的就行，而第二行输出要求的是装满时候的价值。在体积是5条件下，第一种可以选1号物品和3号物品，它们价值就是10+4=14；第二种可以选择2号和3号，它们价值就是5+4=9，第一行输出没有要求背包装满，所以选择第一种方式就行。第二行输出是背包恰好装满的情况，就选择第二种情况。

而输出背包必须装满的情况可能是不存在的，就像例2：给的三个物品体积凑不出来体积为8的情况。

二、算法原理：（1）先来做第一行返回值：

状态表示以某一个位置为结尾如果用dp[i]来表示从前i个物品中选择，在所有选择中的最大价值，但是还得考虑体积的大小。所以这里的状态表示是： dp[i][j]：从从前i个物品中选择，总体积不超过j的所有选择中，能挑出来的最大价值。
状态转移方程根据最后一步的状况，分情况讨论。第一种情况：不选择i物品，那么就是在i-1里面选择，并且体积也依旧小于j,所以就是dp[i-1][j]

第二种情况：选择i物品，那么必须有w[i]，实现的价值最大，就得从i-1里面挑价值最大的出来，并且此时体积要改变，所以到这里的体积必须能够装下v[i]，到i-1位置体积就必须小于j-v[i]，所以这里的状态表示就是w[i]+dp[i-1][j-v[i]] 然后求这两种情况下的最大值就可以了。

初始化 dp表从1开始计数，就多了一行和一列。要保证第一行和第一列填表正确，物品从0中选就是0，体积从0中挑还是0，所以初始化为0就行。
填表顺序它依赖它的上一行位置，i-1表示的是上一行，从上往下
返回值

返回dp[n][v] （2）先来做第一行返回值：

状态表示只需要v的位置正好等于j就行 dp[i][j]：从从前i个物品中选择，总体积正好等于j的所有选择中，能挑出来的最大价值。
状态转移方程第一种情况：不选择i物品，那么就是在i-1里面选择，并且体积也依旧小于j,所以就是dp[i-1][j]，但是这里j可能凑不到总体积，就用一个dp[i][j]=-1来表示这样的情况，所以得先判断dp[i][j]是不是等于-1，所以这种情况就不选择。

第二种情况：选择i物品，那么必须有w[i]，实现的价值最大，就得从i-1里面挑价值最大的出来，并且此时体积要改变，所以到这里的体积必须能够装下v[i]，到i-1位置体积就必须小于j-v[i]，但是这里必须判断dp[i][j]是不是等于-1，所以这里的状态表示就是dp[i][j]不是等于-1情况下w[i]+dp[i-1][j-v[i]]

初始化第一个位置没有物品直接物品和体积都是0,第一行[0,1]位置没有物品，想要凑成体积是1是不可能的，所以第一行剩下的位置就初始化为-1。第一列表示想要把体积正好凑成0，那么不选就是0，就初始化为0就行

填表顺序从上往下
返回值先得判断一下dp[n][V]是不是等于-1，如果是就返回0，不是就返回dp[n][V]

3. 代码

#include <cstring>
#include <iostream>

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

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;
}
// 64 位输出请用 printf("%lld")

4. 优化

利用滚动数组做空间上的优化
代码在原基础上修改即可

在填第i行的时候，仅想要i-1行就可以。就是说要填第1行的数据就需要第0行的数据，第1行填完之后，第0行就没有用了，需要这一行变得有用，就把这一行滚动到第2行，然后利用第1行的值来填第2行，以此类推，就可以更新完这个dp表。

所有这里只需要用到数组就只用到一维。

遍历顺序要改为从右往左。

5. 优化后代码

删除所有横坐标，遍历顺序从右往左

#include <cstring>
#include <iostream>

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

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;
}
// 64 位输出请用 printf("%lld")

注意：