HDU 2546 飯卡（01背包） 解題報告

昨天吧背包九講中最基礎的01背包看完，做了2602。結果晚上比賽相同題目卻做不出。。苦想幾個小時。。。
解題思路：要使剩余錢最少，應該留下塊錢買最貴的東西（標記為t）（注意金額m<5 的情況！！） 接下來就是用剩下的m-5元買除t以外的菜。每種菜只能買一次。就構成背包問題。

代碼：

[cpp]
#include<stdio.h> 
#include<math.h> 
#include<string.h> 
#include<stdlib.h> 
#include<algorithm> 
#include<iostream> 
using namespace std; 
int main() 
{ 
    int n,m,w[1050],v[1050]; 
    while(scanf("%d",&n) && n) 
    { 
        memset(v,0,sizeof(v)); 
        int ma=0,t,i,s=0; 
        for(i=1;i<=n;i++) 
        { 
            scanf("%d",&w[i]); 
            if(w[i]>ma){ma=w[i]; t=i;} 
        } 
        scanf("%d",&m); 
        if(m<5) 
        { 
            printf("%d\n",m); 
            continue; 
        } 
        for(i=1;i<=n;i++) 
        { 
            for(int j=m;j>=w[i];j--) 
            { 
                if(i!=t && v[j-w[i]]+w[i]>v[j]) 
                    v[j]=v[j-w[i]]+w[i]; 
            } 
             
        } 
        printf("%d\n",m-v[m-5]-ma); 
    } 
    return 0; 
}