题目

思路

代码

输入格式

输出格式

数据范围

输入样例

输出样例：

如果你没有动态规划基础请先看动态规划基础

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。最多一次 (这个就是01背包问题的主要特点了)

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

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

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

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

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

0<N,V≤1000
0<vi,wi≤1000

其实思路很简单，就是构造一个网格，举个例子：

就用样例数据，构建好的dp数组为：

构造的状态就是dp[i][j]，在可选 i 件物品，且有 j 的容量的情况下的最大价值。

我们先维护 i 也就是将有 i 件物品的所有容量情况计算出来。当新添加一个物品是，有如下两种操作：

不拿

不拿就相当于是没有新添加这件物品，它就是等于没有这个物品在这个容量时的价值。

即 dp[i][j] = dp[i-1][j]
拿

拿了的话容量就会减少，我们要先判断是否可以拿，所以需要先判断容量 j >= vi 时才可拿

如果可以拿就要判断拿了之后价值是否会有提升，拿了之后容量变成了 j - vi ，所以就相当于当前物品的价值加上没有这个物品且容量为j - vi时的最优价值。即dp[i][j] = dp[i-1][j-vi] + wi

最终还要判断到底拿不拿，就是一个比较就行啦，所以维护状态，或者说状态转移方程就是：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-vi] + wi)

可选物品1（1，2）

可选物品2（2，4）

可选物品3（3，4）

可选物品4（4，5）

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int n, v;   // n 个点， v的最大体积
int w[N][2],dp[N][N]; // 读入的权重数组，动态规划数组

int main () {
    // 读入数据
    cin >> n >> v;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i][0] >> w[i][1];
    }
    // 初始化dp数组
    memset(dp, 0, sizeof(dp));
    // 执行dp操作
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= v; ++j) {
            dp[i][j] = dp[i-1][j]; // 先不拿
            // 如果要第 i 件物品，需要先判断空间够不够
            if (j >= w[i][0]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i][0]] + w[i][1]);
            }
        }
    }
    cout << dp[n][v] << endl;
    return 0;
}