贪心：最贵的留到最后买。 状态转移方程：dp[j]=dp[j a[i]]|dp[j]，dp[i]表示余下i元。
原来就不足5元，那就不能买啦。
代码语言：javascript复制#include<cstdio>
#include<cstring>
#include <algorithm>
using namespace std;
int n, p, a[1001], dp[1001], ans;
int main()
{
while(scanf("%d", &n),n)
{
for(int i = 1; i <= n; i )
scanf("%d", &a[i]);
scanf("%d", &p);
sort(a 1,a n 1);
memset(dp,0,sizeof dp);
dp[p]=1;
for(int i=1;i<n;i )
for(int j=5;j<=p-a[i];j )
dp[j]=dp[j a[i]]|dp[j];
for(int i=5;i<=p;i )if(dp[i])
{
ans=i-a[n];
break;
}
if(p<5)ans=p;
printf("%dn",ans);
}
return 0;
}
