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

￡神魔★判官ぃ 2024-04-27 06:49 89阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]  
> 欢迎 点赞? 收藏✨ 留言✉ 加关注?本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[手撕算法系列专栏][Link 2]】【[LeetCode][]】  
> ?本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助  
> ?希望我们一起努力、成长，共同进步。  
> ![在这里插入图片描述][530b2fdc59bf45d5bfa43fd373793841.png]

**原题链接**：[点击直接跳转到该题目][Link 3]

#### 目录 ####

*  1️⃣题目描述
 *  2️⃣题目解析
 *  3️⃣解题代码

## 1️⃣题目描述 ##

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

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

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

![在这里插入图片描述][c22c38f8debb4358abc1cf8ed555750e.png]

## 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<iostream>
    #include<algorithm>
    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;
    }

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

#include<iostream>
    #include<algorithm>
    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;
    }

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[LeetCode]: https://blog.csdn.net/m0_74352571/category_12252087.html
[530b2fdc59bf45d5bfa43fd373793841.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/6a665672157c4701af30a0bbbfd25893.png
[Link 3]: https://www.acwing.com/problem/content/2/
[c22c38f8debb4358abc1cf8ed555750e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/887ec9bc92ee4e5eb80f6da92d711f87.png