中文题,题意自己看。
思路:
1.如果一开始钱少于5元,不买东西,按原值输出;
2.否则,先拿这五块钱买最贵的一份菜(输入菜的价格后用sort排序一下),然后对其它n-1个菜进行0-1背包处理
View Code
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; bool dp[1001]; int a[1001]; int main() { int i, j, n, m; while(~scanf("%d",&n)&&n) { for(i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); scanf("%d",&m); memset(dp,0,sizeof(dp)); dp[0]=1; if(m<5){printf("%d\n",m);continue;} //注意要考虑m<5的时候 m-=5; //总量减5 for(i=1;i<n;i++) { for(j=m;j>=a[i];j--) if(dp[j-a[i]])dp[j]=1; } for(i=m;i>=0;i--) if(dp[i])break; printf("%d\n",m-i+5-a[n]); } return 0; }