饭卡------HDOJ杭电2546(还是01背包!!!!!!)
01 还是 ------ 背包 杭电 hdoj
2023-09-14 09:07:58 时间
Problem Description
电子科大本部食堂的饭卡有一种非常诡异的设计,即在购买之前推断剩余金额。
假设购买一个商品之前,卡上的剩余金额大于或等于5元,就一定能够购买成功(即使购买后卡上剩余金额为负),否则无法购买(即使金额足够)。所以大家都希望尽量使卡上的剩余金额最少。
某天,食堂中有n种菜出售。每种菜可购买一次。
已知每种菜的价格以及卡上的剩余金额,问最少可使卡上的剩余金额为多少。
Input
多组数据。对于每组数据:
第一行为正整数n。表示菜的数量。n<=1000。
第一行为正整数n。表示菜的数量。n<=1000。
第二行包含n个正整数。表示每种菜的价格。价格不超过50。
第三行包含一个正整数m,表示卡上的剩余金额。m<=1000。
n=0表示数据结束。
Output
对于每组输入,输出一行,包括一个整数。表示卡上可能的最小剩余金额。
Sample Input
1 50 5 10 1 2 3 2 1 1 2 3 2 1 50 0
Sample Output
-45 32
这道题吧,怎么说呢?比起那个骨头那题是有点处理数据的技巧,只是也没什么,以下就来分析一下:
我们先把数据排序,找到最大的那个数maxn,作为来减的数,sort还有什么的即可了。m作为饭卡剩余金额,由于题目以5为分界线,所以m-=5。
然后就是我们最最主要的01背包啦。!
!
!!!
for(i=1;i<n;i++) { for(j=m;j>=price[i];j--) { dp[j]=max(dp[j],dp[j-price[i]]+price[i]); } }
这里dp[m]存储的是能减到最接近5,但是又大于等于5的数,然后输出这样写即可了:
printf("%d\n",m+5-dp[m]-maxn);嗯,大概就是这样。主要就是那个循环,理解然后运用即可了!
!!!。!
语言描写叙述可能不是非常清晰,大伙凑合看吧;
以下贴下AC代码:
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; int main() { int i,j,k; int t,n,m; int maxn; int dp[2014]={0},price[2014]={0}; while(scanf("%d",&n)!=EOF,n) { memset(price,0,sizeof(price)); memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) { cin>>price[i]; } cin>>m; if(m<5) { printf("%d\n",m); continue; } sort(price+1,price+n+1); maxn=price[n]; m=m-5; for(i=1;i<n;i++) { for(j=m;j>=price[i];j--) { dp[j]=max(dp[j],dp[j-price[i]]+price[i]); } } printf("%d\n",m+5-dp[m]-maxn); } return 0; }
写代码能力有限,如有编程爱好者发现BUG。还请指出,不胜感激!
!。!
!
!
相关文章
- 01- Shell脚本学习--入门
- Java实现 蓝桥杯 算法提高 01背包
- 01-学习 Kuber 的 SocialBadge 好榜样 | 02.技术预研 | Social
- delphi xe 之路(19)clientdataset的详细介绍01
- interview 01
- 机器学习入门01 - 框架处理(Framing)
- 读书笔记--SQL必知必会01--了解SQL
- [ES6] 01. Intro to ES6 and traceur compiler
- Hadoop课程-01
- 01表盘控件-08时钟仪表盘-gaugeclock
- 【MyBatis笔记01】MyBatis框架介绍以及开发环境搭建
- “2021-01-30T16:00:00.000Z“: expected format “yyyy-MM-dd HH:mm:ss“时间戳格式化
- jquery中的选择器01
- FPGA-(任务01)设计一个三位二进制减法计数器
- 数字信号处理-01- 数字信号处理基础知识
- HLS介绍 - 01 - FPGA的架构、结构以及硬件设计相关概念
- spinal HDL - 01 - 环境搭建与Scala编程指南
- (01)ORB-SLAM2源码无死角解析-(33) ORB特征匹配→局部建图BoW加速匹配,三角化SearchForTriangulation
- 【第01天】A + B | 基础输入输出,开启学习Java旅程