01背包问题c++

问题

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

讲解

首先要说明的就是，本教程只讲解一般的写法，不讲解优化方法（滚动数组降维），先把基本的思想学会了，然后再去学优化方法的。
相信大多数人刚开始学dp问题的时候碰到的就是01背包问题，dp问题首先就是先定义dp数组所代表的意义（比如说这道题，dp[i][j]所代表的就是选取前i个物品体积不会超过j的最大价值），然后就是判断每一步的状态（比如说这一题就是每一步都要判断是否选择这个物品），然后就是状态转移方程了。
回归本题目，本题的思想就是装前i个物品，然后体积一直增大，每次就是判断选不选这个物品，

• 如果选这个物品的价值就是dp[i - 1][j - v[i]] + w[i]
  解析：选这一个那么肯定要加上这一个的价值w[i]这里应该没有问题了吧，那为什么前面是dp[i - 1][j - v[i]]呢？因为就是选了这一个物品了，这一个物品占据了v[i]的体积，那么只要找到子问题选i-1个物品，然后体积不大于j-v[i]的最优解就可以了。
• 如果不选这个物品，就直接从前i-1个物品选体积不大于j的最优解了。
• 每次判断一下，就是如果这个物品的体积大于现在所能装的最大的体积，那么肯定就是直接不能选择这个物品了。

图解

• 图片中在中间价值数据中被标黄的数据就是当前物品的体积大于背包当前所能装的最大体积，所以直接就不用选这个物品，直接将上一层的数据拉下来就行了。
• 图片可能会不好看哈，等我优化。
  

基础源码

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, k;
int v[N], m[N];
int dp[N][N];

int main()
{
    cin >> n >> k;

    for (int i = 1; i <= n; i ++ ) cin >> v[i] >>m[i];

    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= k; j ++ )
        {
            if (v[i] > j)
            {
                dp[i][j] = dp[i - 1][j];
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j - v[i]] + m[i], dp[i - 1][j]);
            }
        }
    }

    cout << dp[n][k] << endl;

}

一维数组优化

• 来自几个小时后的我：看了一下y总的视频，突然就会了一维数组的优化方法是怎么写的了。
• 其实如果上面那个图你从头推了一遍，你就会发现我们更新每一层的数据的时候，其实只用到了上一层的数据而且还是用到上一层数据的范围为-->从上一层起点开始到本层数据正上方的数据。比如说我们要更新第三层第4列的数据，那么其实我们用到的数据范围为，第3-1层第一列到第3-1层第4列。
• 我们遍历j的时候要从后（最大的体积）向前遍历到v[i]。
  • 为什么要从后开始遍历呢？
    因为我们每次更新要用到前面的数据，如果我们从前向后更新，当我们遍历到后边的时候要用到前面的数据但是前面的数据已经更改了，不是第i-1层的数据了，所以我们要从后向前遍历，这样就不会影响到前面的数据。
  • 为什么遍历到v[i]就可以了呢？
    因为就是j<v[i]的时候肯定是不能选这个物品的，直接就是拉取正上方的数据就行，也就相当于不用更改数据。

一维数组优化后源码

#include <iostream>

using namespace std;

const int N = 1010;

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

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++ )
    {
        for (int j = m; j >= v[i]; j -- )
        {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }

    cout << dp[m] << '\n';

    return 0;

}