【算法|动态规划No.31 | 01背包问题】01背包模板题

个人主页：兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

原题链接：点击直接跳转到该题目

1️⃣题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

2️⃣题目解析

状态表示：

• dp[i][j] 表示从前i个物品中进行挑选，体积不超过j的情况下的最大价值。

状态转移方程：

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

注意：这里dp[i - 1][j]的情况是一定存在的；而dp[i - 1][j - V[i]] + W[i]的情况只有在j >= V[i]时才会存在。

空间优化：注意填dp表时需要从右往左填。

3️⃣解题代码

解法1（朴素算法：二维dp）

#include
#include
using namespace std;

const int N = 1010;
int V[N],W[N],dp[N][N];

int main()
{
    int n,v;
    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] >= 0) dp[i][j] = max(dp[i][j],dp[i - 1][j - V[i]] + W[i]);
        }
    }
    cout << dp[n][v] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

解法2（滚动数组空间优化）：

#include
#include
using namespace std;

const int N = 1010;
int V[N],W[N],dp[N];

int main()
{
    int n,v;
    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] >= 0;j--)
             dp[j] = max(dp[j],dp[j - V[i]] + W[i]);
    cout << dp[v] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19