【ETOJ P1024】无穷背包题解（动态规划+完全背包）

本文主要是介绍【ETOJ P1024】无穷背包题解（动态规划+完全背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

小 $e$ 的背包容量为 $m$ ，现在商店里有 $n$ 种商品。由于在梦境中，他可以零元购，商店里的每种商品都有无穷件，每件商品有一个价值 $w_i$ 和体积 $v_i$ 。

问小 $e$ 最多可以带走多少价值的商品？

输入

第一行两个整数表示 $m, n$ 。（ $1 ≤ m ≤ 10^5, 1 ≤ n ≤ 500$ ）

接下来 $n$ 行，每行两个整数表示 $w_i, v_i$ 。（ $1 ≤ w_i ≤ 10^9, 1 ≤ v_i ≤ m$ ）

输出

一行一个整数表示答案。

样例输入

样例输出

提示

解释：拿两件物品3，再拿两件物品1，得到价值最大为24。

思路

首先，读取背包容量 $m$ 和商品种类数 $n$ ，然后读取每种商品的价值和体积。动态规划数组 dp 被定义来存储在给定背包容量下可以获得的最大价值。dp[j] 表示背包容量为 $j$ 时的最大价值。

然后，对于每种商品 $i$ ，从其体积 $v_i$ 到 $m$ 遍历背包的容量 $j$ 。如果选择了商品 $i$ ，背包的容量会减少 $v_i$ ，但是可以增加 $w_i$ 的价值。因此，dp[j] 被更新为 dp[j] 和 dp[j - v[i]] + w[i] 中的较大值，这表示在背包容量为 $j$ 时，选择或者不选择商品 $i$ 的两种情况下的最大价值。

最后，输出 dp[m]，即在背包容量为 $m$ 时，可以获得的最大价值。

AC代码

#include <algorithm>
#include <iostream>
#define ll long long
#define AUTHOR "HEX9CF"
using namespace std;const int N = 1e6 + 7;int m, n;
int w[N], v[N];
ll dp[N];int main() {cin >> m >> n;for (int i = 1; i <= n; i++) {cin >> w[i] >> v[i];}for (int i = 1; i <= n; i++) {for (int j = v[i]; j <= m; j++) {dp[j] = max(dp[j], dp[j - v[i]] + w[i]);}}cout << dp[m] << endl;return 0;
}