思路:

最贵的菜一定是最后一次购买使餐卡上剩下的钱最小。

输入如果小于5的话直接输出～

不然先从所有菜中找出最贵的菜，然后给餐卡至少留下5块钱买这个最贵的菜，剩下的用一个0-1背包去装满!

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #define sc(x) scanf("%d",&(x)) 6 #define pf(x) printf("%d\n", x) 7 #define CL(x, y) memset(x, y, sizeof(x)) 8 #define max(a, b) (a > b ? a : b) 9 using namespace std;10 const int MAX = 1005;11 int dp[MAX], money[MAX];12 int n, m;13 int main ()14 {15     int i, j;16     while(sc(n))17     {18         if(n == 0) break;19         CL(dp, 0);20         for (i = 0; i < n; i++)21             sc(money[i]);   //价格22         sc(m);  //卡上的余额23         sort(money, money+n);     //排序，求前n-1个钱价的最大钱数24         if (m < 5)25             pf(m);26         else27         {28             for (i = 0; i < n-1; i++)    //01背包问题29                 for (j = m-5; j >= money[i]; j--)30                     dp[j] = max(dp[j], dp[j-money[i]] + money[i]);31             pf(m - dp[m-5] - money[n-1]);   //money[n-1] 最后一个价格32         }33     }34     return 0;35 }