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

补充：软件开发 , C++ ,

上一个：《Effective C++》构造函数析构函数Assignment运算符
下一个：poj1125Stockbroker Grapevine - floyd最短路