本文主要是介绍【ETOJ P1024】无穷背包 题解（动态规划+完全背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
小 e e e 的背包容量为 m m m，现在商店里有 n n n 种商品。由于在梦境中，他可以零元购，商店里的每种商品都有无穷件，每件商品有一个价值 w i w_i wi 和体积 v i v_i vi。
问小 e e e 最多可以带走多少价值的商品？
输入
第一行两个整数表示 m , n m, n m,n。（ 1 ≤ m ≤ 1 0 5 , 1 ≤ n ≤ 500 1 ≤ m ≤ 10^5, 1 ≤ n ≤ 500 1≤m≤105,1≤n≤500）
接下来 n n n 行，每行两个整数表示 w i , v i w_i, v_i wi,vi。（ 1 ≤ w i ≤ 1 0 9 , 1 ≤ v i ≤ m 1 ≤ w_i ≤ 10^9, 1 ≤ v_i ≤ m 1≤wi≤109,1≤vi≤m）
输出
一行一个整数表示答案。
样例输入
10 3
2 1
5 3
10 4
样例输出
24
提示
解释：拿两件物品3，再拿两件物品1，得到价值最大为24。
思路
首先，读取背包容量 m m m 和商品种类数 n n n，然后读取每种商品的价值和体积。动态规划数组 dp 被定义来存储在给定背包容量下可以获得的最大价值。dp[j] 表示背包容量为 j j j 时的最大价值。
然后，对于每种商品 i i i，从其体积 v i v_i vi 到 m m m 遍历背包的容量 j j j。如果选择了商品 i i i，背包的容量会减少 v i v_i vi，但是可以增加 w i w_i wi 的价值。因此，dp[j] 被更新为 dp[j] 和 dp[j - v[i]] + w[i] 中的较大值，这表示在背包容量为 j j j 时，选择或者不选择商品 i i i 的两种情况下的最大价值。
最后，输出 dp[m]，即在背包容量为 m 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;
}
这篇关于【ETOJ P1024】无穷背包 题解（动态规划+完全背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
