A18648. 基础01背包求解
填空题
较难
知识点
题目描述
基础01背包求解
题目描述
给定一个背包的最大容量 C，以及 n 个物品，每个物品有对应的重量 w[i] 和价值 v[i]。每个物品只能选择放入背包一次或不放，请求出背包能装载的最大总价值。
输入格式
1. 第一行输入两个整数 n（物品数量）和 C（背包容量），1≤n≤20，1≤C≤100；
2. 第二行输入 n 个整数，代表每个物品的重量；
3. 第三行输入 n 个整数，代表每个物品的价值。
输出格式
输出一个整数，表示背包可装载的最大价值。
样例输入
4 8
2 3 4 5
3 4 5 6样例输出
9参考答案
#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];
// 01背包一维核心逻辑
for(int i = 1; i <= n; i++)
{
for(int j = C; j >= w[i]; j--)
{
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[C] << endl;
return 0;
}答案解析
评分标准（50分）：
1. 正确完成输入输出、数组定义（10分）；
2. 正确写出01背包倒序容量遍历（15分）；
3. 状态转移方程书写正确（15分）；
4. 代码无bug、样例输出正确、可正常编译运行（10分）；
上一题
下一题