01 背包。。。

1.   hdu    饭卡

      分析：    1，当卡上金额小于5元时，不能买任何菜。

                       2，否则，状态转移方程： f[ j ] = max ( f [ j ] , f [ j -price [ i ] ]+price [ i ] );      f [ j ]表示买第 i个菜时的预算为 j = m-5 时的最大开销。

                        排序是为了选出最贵的菜，可以不排序直接选。

             sort(W+1,W+n+1);
            m=m-5;
            for(int i=1;i<n;i++)
            {
                for(int j=m;j>0;j--)
                 if(j>=W[i]) dp[j]=max(dp[j],dp[j-W[i]]+W[i]);
            }
            printf("%d\n",m+5-dp[m]-W[n]);

01 背包。。。

原文：http://blog.csdn.net/u013514722/article/details/41408475