01背包---点菜问题
--- 01 背包 问题
2023-09-11 14:22:51 时间
https://www.nowcoder.com/questionTerminal/b44f5be34a9143aa84c478d79401e22a
#include<cstdio> #include<iostream> #include<string> #include<cstring> #include<cmath> #include<stdlib.h> #include<algorithm> #include<vector> #include<queue> #include<stack> #include<iomanip> using namespace std; //菜的价格、评分 int dp[105][1005]; //前几个菜,剩余的金额 int jiage[105]; int defen[105]; int main() { int C,N; while(cin>>C>>N) { for(int i=1;i<=N;i++) { cin>>jiage[i]>>defen[i]; } for(int j=0;j<=C;j++) dp[0][j]=0; for(int i=0;i<=N;i++) dp[i][0]=0; for(int i=1;i<=N;i++) for(int j=1;j<=C;j++) { if(j>=jiage[i]) { dp[i][j]=max(dp[i-1][j],dp[i-1][j-jiage[i]]+defen[i]); } else dp[i][j]=dp[i-1][j]; } cout<<dp[N][C]<<endl; } return 0; }
注意后面两个循环是从1开始的。
红色部分易错。
简化方法:
dp[i][j]的转移仅与二维数组中本行的上一行有关,可以优化成一维数组。
dp[j]=max(dp[j],dp[j-jiage[i]]+defen[i]);
#include<cstdio> #include<iostream> #include<string> #include<cstring> #include<cmath> #include<stdlib.h> #include<algorithm> #include<vector> #include<queue> #include<stack> #include<iomanip> using namespace std; //菜的价格、评分 int dp[1005]; //前几个菜,剩余的金额 int jiage[105]; int defen[105]; int main() { int C,N; while(cin>>C>>N) { for(int i=1;i<=N;i++) { cin>>jiage[i]>>defen[i]; } for(int j=0;j<=C;j++) dp[j]=0; for(int i=1;i<=N;i++) for(int j=C;j>=jiage[i];j--) { dp[j]=max(dp[j],dp[j-jiage[i]]+defen[i]); } cout<<dp[C]<<endl; } return 0; }
必须保证在每次更新时,dp[j-jiage[i]]没有被更新,所以dp[j]遍历是倒序
相关文章
- Android 开源框架Universal-Image-Loader完全解析(二)--- 图片缓存策略详解
- ExtJS--学习--window窗体属性--解决重复窗体事件---子组件的添加---工具条tbar
- Java学习---程序设计_面试题[2]
- 山东理工大学ACM平台题答案关于C语言 1137 C/C++经典程序训练7---求某个范围内的所有素数
- verilog基础---运算符优先级
- ActiveReports 报告应用程序教程 (2)---上市类报告
- 匀速运动实例---分享到
- [Python]队列---双向队列实现介绍及应用
- 《Linux命令行与shell脚本编程大全 第3版》Shell脚本编程基础---01
- 标准C程序设计七---01
- 02数据结构与算法分析之---数据的两种结构
- 23深入理解C指针之---数组的基础