这是一道01背包问题，但是需要预处理一下，因为当你的钱不够5块钱的时候，你什么都买不了，所以直接输出钱数，当你的钱大于5块钱的时候，你可以先拿出来5块钱，留着最后去买最贵的菜，现在你剩下m-5块钱，排个序把最贵的留在最后,然后就用01背包把这m-5尽量装满(遍历1~n-1种菜，因为n是最贵的菜要留给最后)，然后再用那剩下的5块钱去买最贵的菜，最后就是最优解m-dp[m-5]-dp[n]。我写的代码是从0开始的，所以最后的解是m-dp[m-5]-dp[n-1]，理解就好。。
AC代码：
代码语言：javascript复制#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
int dp[MAXN];
int c[MAXN];
int n,m;
int main()
{
while(~scanf("%d",&n)){
if(n==0) break;
for(int i=0;i<n;i ){
scanf("%d",&c[i]);
}
sort(c,c n); // 这里排一下序，因为要用5块钱去买最贵的，所以把最贵的放在后面方便点
memset(dp,0,sizeof(dp));
scanf("%d",&m);
if(m<5){cout<<m<<endl;} // 当钱少于5的时候直接输出
else{
for(int i=0;i<n-1;i ){ // 遍历n-1次，把最贵的跳过
for(int j=m-5;j>=c[i];j--){ // 钱数应该-5
dp[j] = max(dp[j],dp[j-c[i]] c[i]);
}
}
printf("%dn",m - c[n-1] - dp[m-5]); // m是总钱数，c[n-1]是最贵的菜，dp[m-5]是当前最贵的状态
}
}
return 0;
}
/*
[来源] HDU 2546
[题目] 饭卡
[大意]
有一张饭卡，买饭的之前需要判断一下是不是大于5，小于5的话就不能买了，直接输出这个钱数就好了，大于5的
话，先排一下序，然后按01背包写就好，具体过程看代码注释吧。
[输入]
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0
[输出]
-45
32
*/
