饭卡
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4443 Accepted Submission(s): 1533
Problem Description
电子科大本部食堂的饭卡有一种很诡异的设计,即在购买之前判断余额。如果购买一个商品之前,卡上的剩余金额大于或等于5元,就一定可以购买成功(即使购买后卡上余额为负),否则无法购买(即使金额足够)。所以大家都希望尽量使卡上的余额最少。
某天,食堂中有n种菜出售,每种菜可购买一次。已知每种菜的价格以及卡上的余额,问最少可使卡上的余额为多少。
某天,食堂中有n种菜出售,每种菜可购买一次。已知每种菜的价格以及卡上的余额,问最少可使卡上的余额为多少。
Input
多组数据。对于每组数据:
第一行为正整数n,表示菜的数量。n<=1000。
第二行包括n个正整数,表示每种菜的价格。价格不超过50。
第三行包括一个正整数m,表示卡上的余额。m<=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
Source
Recommend
lcy
真正意义上的第一道做出来01背包的题目,想了半天才AC,AC了也还糊里糊涂的。。。。
先要对菜钱从小到大排序,不排序会出错。。
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define MAXN 1001 int c[MAXN]; int f[MAXN]; int main(void) { int n; while(scanf("%d",&n),n) { int i,j; for(i=1;i<=n;i++) scanf("%d",&c[i]); sort(c+1,c+n+1); memset(f,-1,sizeof(f)); //f[i]=-1代表该余额未出现过 int m; //f区间表示余额的范围 scanf("%d",&m); m+=50; //余额存在负值,对区间进行映射!! f[m]=1; for(i=1;i<=n;i++) for(j=55;j<=m;j++) { if(f[j]!=-1) { f[j-c[i]]=1; //标记余额i已出现 // printf("%d\n",j-c[i]); } } for(i=1;i<=1050;i++) if(f[i]==1) break; printf("%d\n",i-50); } return 0; }
ZeroClock :
解题思路:本题可套用01背包的思想,值是价值变为可达不可达。用dp[j]表示余额为j是否可达,可达为1,否则为0.
状态转移方程为if (dp[j] && j - price[i] >= 5) dp[j-price[i]] = 1;然后记录转移到最小值,最后输出即可。
本题有两个地方需要注意:1、遍历余额的顺序要从0到sum,这样转移的时候都是利用前一次的结果,因为sum是初状态和01背包里的0状态一样。 2、price必须事先经过排序,否则前面大的先转移到5以下,后面小的就没办法更新了。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define MAX 100000 int n,price[MAX]; int sum,minn,dp[MAX]; int main() { int i,j,k,t; while (scanf("%d",&n) ,n) { for (i = 1; i <= n; ++i) scanf("%d",&price[i]); scanf("%d",&sum); sort(price+1,price+1+n); memset(dp,0,sizeof(dp)); dp[sum] = 1,minn = sum; for (i = 1; i <= n; ++i) for (j = 5; j <= sum; ++j) if (dp[j] == 1) { if (j - price[i] >= 5) dp[j-price[i]] = 1; if (j - price[i] < minn) minn = j - price[i]; } printf("%d\n",minn); } }