思路:
题目的意思:如果购买一个商品之前,卡上的剩余金额大于或等于5元,就一定可以购买成功(即使购买后卡上余额为负),否则无法购买(即使金额足够)
如果要使卡上的剩余金额最少,则假设最后剩下5元,肯定是买最贵的一种,则可以在卡最初的剩余金额上欲留出5元,最后买最贵的,所以要事先排好序(菜的金额从小到大),然后卡上剩下的金额可以购买除最贵的菜的所有的菜,使其达到最大价值(通过0/1背包求解)
AC代码如下:
#include<stdio.h> #include<string.h> #include<stdlib.h> int dp[1005],c[1005]; int V; int cmp(const void *a,const void *b) { return *(int *)a-*(int *)b; } void ZeroOnePack(int c,int w) { int v; for(v=V-5;v>=c;v--) if(dp[v]<dp[v-c]+w) dp[v]=dp[v-c]+w; } int main() { int n; int i; while(scanf("%d",&n)!=-1&&n) { for(i=1;i<=n;i++) scanf("%d",&c[i]); scanf("%d",&V); if(V<5) { printf("%d\n",V); continue; } qsort(c+1,n,sizeof(c[1]),cmp); memset(dp,0,sizeof(dp)); for(i=1;i<n;i++) ZeroOnePack(c[i],c[i]); printf("%d\n",V-dp[V-5]-c[n]); } return 0; }