原题链接:Bessie的体重问题
解题思路:01背包
注意事项:测试数据有误, hack AC
参考代码:
#include<bits/stdc++.h> using namespace std; const int N = 5e4 + 10; // 定义最大容量上限,根据题目需求设置 int dp[N]; // dp[j]表示容量为j时能获得的最大价值 int a[N]; // 存储物品的重量(此处价值与重量相同) int n, m; // n为背包最大容量,m为物品数量 int main() { cin >> n >> m; // 输入背包容量n和物品数量m for(int i = 0; i < m; ++i ) cin >> a[i]; // 输入每个物品的重量(价值等于重量) // 动态规划核心:采用逆序遍历避免物品重复使用(0-1背包特性) for(int i = 0; i < m; ++ i) // 遍历每个物品 // 从背包最大容量开始逆序遍历到当前物品重量 for(int j = n; j >= a[i]; j--) // 状态转移方程: // 不选当前物品:dp[j]保持不变 // 选当前物品:dp[j - a[i]] + a[i](容量j-a[i]的最大价值加上当前物品价值) dp[j] = max(dp[j], dp[j - a[i]] + a[i]); // 输出容量为n时的最大价值 cout << dp[n]; return 0; }
0.0分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复