HDOJ 饭卡 01背包

水题。不过还是让我wa了几次。原来是在于初始化的问题。罢了罢了。想清楚还是很好的。

去食堂买菜，最贵的是一定要刷卡的。留着刷吧，然后让其余的尽量接近5块钱就好了。和其他人的代码有点不同... 本质是一样的啦。

代价和话费是一样的和那个BIG EVENT AT HDU那题一样。这种解法知道怎么做了。继续切。。。。

#include<iostream>
#include<string>
#include<cstdio>
using namespace std;int max( int a,int b ){ return a>b?a:b; }int main()
{int N,M;int f[1001];int item[1001];while( scanf( "%d",&N ),N ){int max_value=0;memset( f,0,sizeof(f) );int index;for( int i=1;i<=N;i++ ){scanf( "%d",&item[i] );max_value=max( max_value,item[i] );if( max_value==item[i] )index=i;}scanf( "%d",&M );if( M<5 ){printf( "%d\n",M );continue;}f[M]=1;for( int i=1;i<=N;i++ )if( index!=i ){for( int j=0;j+item[i]<=M;j++ )if( f[j+item[i]]==1 )f[j]=1;}int min;for( int i=5;i<=M;i++ )if( f[i]==1 ){min=i;break;}printf( "%d\n",min-item[index] );}return 0;
}