A18637. 基础完全背包求解
填空题
较难
知识点
题目描述
基础完全背包求解
题目描述
给定背包最大容量 C 以及 n 种物品，每种物品有固定重量 w[i] 和价值 v[i]，每种物品可以无限次选取。请计算背包能够装载的最大总价值。
输入格式
1. 第一行输入两个整数 n（物品种类数）和 C（背包容量），1≤n≤20，1≤C≤100；
2. 第二行输入 n 个整数，代表每种物品的重量；
3. 第三行输入 n 个整数，代表每种物品的价值。
输出格式
输出一个整数，表示背包可装载的最大价值。
样例输入
2 8
2 3
3 4样例输出
12参考答案
#include <iostream>
#include <algorithm>
using namespace std;
int dp[105];
int w[25], v[25];
int main()
{
int n, C;
cin >> n >> C;
for(int i = 1; i <= n; i++) cin >> w[i];
for(int i = 1; i <= n; i++) cin >> v[i];
// 完全背包一维核心逻辑：正序遍历容量
for(int i = 1; i <= n; i++)
{
for(int j = w[i]; j <= C; j++)
{
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[C] << endl;
return 0;
}答案解析
采用完全背包一维优化解法，定义dp[j]为容量j的背包可承载的最大价值。
遍历每一种物品，正序遍历背包容量，实现物品重复选取，不断更新最优价值，最终dp[C]即为答案。
本题最优方案：选取4个重量2、价值3的物品，总重量8，总价值12。
上一题
下一题