每日算法打卡：01背包问题 day 13

原题链接

2. 01背包问题

题目难度：简单

题目描述

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

第 iii 件物品的体积是 $v_i$，价值是 $w_i$。

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

输入格式

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

接下来有 N 行，每行两个整数 $v_i,w_i$，用空格隔开，分别表示第 iii 件物品的体积和价值。

输出格式

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

数据范围

$0<N,V\le 1000$
$0<v_i,w_i\le 1000$

输入样例

4 5
1 2
2 4
3 4
4 5 

输出样例：

8 

题目分析

这道题是非常典型的题目，有一类问题都叫背包问题，而这道题目则是最经典的01背包问题，题目的意思也很好理解，最终就是要让背包中的价值最大

这里的01的意思就是，每个物品最多只能使用1次

这里需要用到一个非常重要的分析解决问题的方法叫做动态规划（DP），而这种问题我们也称之为动态规划问题

对于动态规划来说，我们一般从两个方面来考虑，首先就是状态表示，第二个叫做状态计算（转移），所谓的状态就叫做未知数，那么对于背包问题来说就是二维情况下的，状态计算就是如何从已知条件递推出下一个位置的结果

那么对于较难的问题，还需要对代码进行优化，这里我们先不考虑优化

这里状态表示的含义其实可以细分，首先就是集合是什么，也就是这整个数组是什么含义，其次是集合的属性是什么，也就是对应到数组中具体的值的含义，含义是有三种的，最大值，最小值，数量

对背包问题来说，他的数组的含义就是所有选法的集合，有两个条件作为限制，第一是只从前i个物品中选，第二个条件是选出来的物品的总体积需要小于等于j，那么对于每一个数组中的元素来说，他代表的含义就是选出的物品的最大价值

状态计算就对应的是集合划分，对背包问题来讲，就是是否包含第i个物品，这样就可以不重不漏的分划这个集合

那假设我们要计算f(i,j)，他的含义为，从前i个物品中选择物品的总体积不大于j的最大价值

我们可以把它划分成是否包含第i个物品

如果不包含，那么他就等价于从前i-1个物品中选择物品的总体积不大于j的最大价值

如果包含，那么他就等价于从前i-1个物品中选择物品的总体积不大于j的最大价值，再加上第i个物品的价值即可

用数学公式表示就可以是

$f(i,j)=f(i?1,j)$ 不包含

$f(i,j)=f(i?1,j?v_i)+w_i$ 包含

那么最终的结果应该是

f ( i , j ) = max ? { f ( i ? 1 , j ) , f ( i ? 1. j ? v i ) + w i } f(i,j)=\max\{f(i-1,j),f(i-1.j-v_i)+w_i\} f(i,j)=max{f(i?1,j),f(i?1.j?vi?)+wi?}

这就类似于递归的思想，把一个大问题细分成小问题

示例代码

二维

#include<iostream>
using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

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

    // 初始化
    // f[0][0]~f[0][m]=0 当一件物品都没有选择时，最大价值是0，全局初始化因此省略

    // 枚举
    for (int i = 1; i <= n; i++) // 枚举件数
    {
        for (int j = 0; j <= m; j++) // 枚举体积
        {
            f[i][j] = f[i - 1][j]; // 当体积超过了限制时，就不能选第i个物品了，因此f[i][j]至少是可以选择f[i-1][j]的
            if (j >= v[i])
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m] << '\n';
    return 0;
}

一维优化

#include<iostream>
using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    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--) // 枚举体积
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[n][m] << '\n';
    return 0;
}