【动态规划】完全背包
【题目描述】
设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为m，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于m，而价值的和为最大。
【输入】
第一行：两个整数，m(背包容量,m<=200)和n(物品数量n<=30)；
第2....N+1行：每行二个整数Wi,Ci表示每个物品的重量和价值。
【输出】
仅一行，一个数，表示最大总价值。
【输入样例】
10 4 2 1 3 3 4 5 7 9
【输出样例】
max=12
【题目分析】
输入部分：
首先读取两个整数，
m为背包的最大容量，n为物品的数量。接着，通过循环读取每个物品的信息，包括其重量
Wi和价值Ci。动态规划数组：
创建一个长度为
m + 1的数组dp，用于存储在各个可能的背包容量下获得的最大价值。状态转移处理：
外层循环遍历所有的物品（从 0 到 n-1）。
内层循环从当前物品的重量开始迭代到背包的最大容量
m。这是因为，对于无限数量的物品，可以多次选择同一物品，所以这里的内层循环的起始位置应该是weights[i]。在每一步更新
dp[j]时，计算不选择和选择当前物品所能得到的最大价值，并选择较大值进行更新。输出结果：
最后，打印出在背包最大容量
m下的最大总价值。
【参考代码】
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int m, n;
cin >> m >> n; // 读取背包容量 m 和物品数量 n
int weights[30]; // 存放物品重量，大小为最大数量 n
int values[30]; // 存放物品价值，大小为最大数量 n
int dp[201] = {0}; // dp 数组初始化，大小为最大容量 m + 1，初始值为 0
// 读取每个物品的重量和价值
for (int i = 0; i < n; i++) {
cin >> weights[i] >> values[i];
}
// 动态规划处理
for (int i = 0; i < n; i++) {
for (int j = weights[i]; j <= m; j++) { // 从 weights[i] 开始更新
dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
}
}
// 输出最大总价值
cout << "max=" << dp[m] << endl;
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
