hdu 2546

/* 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;
}

hdu 2546,布布扣,bubuko.com

hdu 2546

原文：http://blog.csdn.net/littlefool5201314/article/details/22654333