/* 01背包变型 一开始想的是n<=1000,价格最大为50 所以开了50005的数组
结果发现余额最大1000,所以数组不必开那么大
用5元取一个最大价值的,明显最优,所以先用5元减去一个最大值,就变成了01背包
所以最后输出的时候后 dp[cost-5]和减去一个max
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX(a,b) (a)>(b)?a:b
int dp[1005],a[1005];
int main()
{
int i,j,n,cost,max;
while(scanf("%d",&n),n)
{
for(i=0; i<n; i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&cost);
sort(a,a+n);
max=a[n-1];
memset(dp,0,sizeof(dp));
if(cost<5) printf("%d\n",cost);
else
{
for(i=0; i<n-1; i++)
{
for(j=cost-5; j>=a[i]; j--)
{
dp[j]=MAX(dp[j],dp[j-a[i]]+a[i]);
}
}
printf("%d\n",cost-max-dp[cost-5]);
}
}
return 0;
}
c++中new容易出现的问题,布布扣,bubuko.com
c++中new容易出现的问题