这里5元是个什么意思呢、差不多就是特殊情况了、
就是说最贵的那个东西先不买、并且最后要留下5元去买那个最贵的、
也就是说对现在金钱-5 拿剩下的钱去对减去最贵的商品后的商品dp、看这些剩下的钱能买多少价值的商品
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int qq=+;
int price[qq<<],dp[qq<<];
int main()
{
int n;
while(~scanf("%d",&n)&&n){
memset(price,,sizeof(price)); //初始化
memset(dp,,sizeof(price));
for(int i=;i<n;++i)
scanf("%d",&price[i]);
sort(price,price+n);
int money;scanf("%d",&money);
if(money<){
printf("%d\n",money);
continue;
}
money=money-; //取出5元用于购买最贵的物品、
for(int j,i=;i<n-;++i)
for(j=money;j>=price[i];--j)
dp[j]=max(dp[j],dp[j-price[i]]+price[i]); //物品只有买或者不买两种选择
printf("%d\n",money+-dp[money]-price[n-]);
}
return ;
}