HDOJ 2546 飯卡

  這道題讓我糾結了很久，原來的思想是對的卻又找出了理由否定自己，折騰半天還是相信第一感覺的好。首先找出最大的價格mx，然後讓其它的做0/1背包，讓其總和逼近dp[m-5]，這應該很好理解，最後能買到的最多食物就是dp[m-5]+mx，所以余額為m-dp[m-5]-mx;不過還要判斷m<5的情況就是買不到（題意規定）。

代碼：

[cpp] 
#include<iostream> 
#include<algorithm> 
using namespace std; 
int a[1005],dp[1005]; 
int main() 
{ 
    int n,m,mx,i,j,pt; 
    while( scanf("%d",&n)&&n){ 
           mx=0; pt=0; 
           for( i=1; i<=n; i++){ 
                scanf("%d",&a[i]); 
                if( a[i]>mx){ //選出最大值 
                    mx=a[i]; 
                    pt=i; 
                } 
           } 
           scanf("%d",&m); 
           int temp=a[pt]; 
           a[pt]=a[n]; 
           a[n]=a[pt]; 
           if( m>=5){ 
               memset(dp,0,sizeof(dp)); 
               for( i=1; i<n; i++) //用其余n-1個做0/1背包 
                    for( j=m-5; j>=a[i]; j--) 
                         dp[j]=max(dp[j],dp[j-a[i]]+a[i]); 
               printf("%d\n",m-dp[m-5]-mx); 
           } 
           else 
               printf("%d\n",m); 
    } 
    return 0; 
}