HDOJ 2546 飯卡 (01背包)

題意：卡內有m元錢，有n種菜可以買（每種菜只可以買一次），只要卡內金額大於等於5元就可以買任何菜（刷到負也可以）。求最少可使卡上的余額為多少。
思路：最貴的一個菜一定是最後買，然後用01背包求（m-5）元錢可買的菜的最大金額，然後（m-最大金額-最貴的菜的價錢）即為所求。
[cpp] 
#include<stdio.h> 
#include<string.h> 
 
#define maxn 1111 
 
int val[maxn],f[maxn]; 
 
main() 
{ 
    int n,m,i,j,max,pos; 
    while(scanf("%d",&n)&&n) 
    { 
        for(i=1;i<=n;i++) 
            scanf("%d",&val[i]); 
        scanf("%d",&m); 
        if(m<5) 
        { 
            printf("%d\n",m); 
            continue; 
        } 
        for(max=-1,pos=0,i=1;i<=n;i++) 
            if(max<val[i]) 
            { 
                max=val[i]; 
                pos=i; 
            } 
        memset(f,0,sizeof(f)); 
        for(i=1;i<=n;i++) 
        { 
            if(pos==i) 
                continue;  www.2cto.com
            for(j=m-5;j>=val[i];j--) 
                if(f[j]<f[j-val[i]]+val[i]) 
                    f[j]=f[j-val[i]]+val[i]; 
        } 
        printf("%d\n",m-f[m-5]-max); 
    } 
    return 0; 
} 
作者：sdc1992