首页 > 代码库 > HDU 2546 饭卡

HDU 2546 饭卡

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2546

 

思路:1.如果余额小于5,直接输出,因为小于5买不了任何东西

   2.如果余额大于5,

    (1)则对所有的菜进行排序,选出其中最大的一个

    (2)将余额减去5,然后在上面进行01背包。(如果定义余额为s,那么体积为s-5,物品个数为n-1,为什么是n-1呢,因为我们在第一步中去掉了一个最大的)

    (3)将余额减去01背包的结果再减去那个最大的菜即可(即 余额-(结果+最大的菜))

 

代码用一维数组或者二维数组做均可。

代码如下:

    

#include <iostream>#include <cstring>#include <algorithm>using namespace std;int dp[1001]; inline int max6(int a,int b){ return a>b?a:b;}int main(){    int n,s;    int v[1001];    int i,j;    int max;    while(cin>>n&&n!=0)    {        memset(dp,0,sizeof(dp));        memset(v,0,sizeof(v));        for(i=1; i<=n; i++)        {            cin>>v[i];        }                cin>>s;            sort(v,v+n+1);                if(s<5)        {            cout<<s<<endl;            continue;        }                                for(i=1;i<n; i++)        {            for(j=s-5; j>=v[i]; j--)                    dp[j] = max6(dp[j],dp[j-v[i]]+v[i]);        }                cout<<s-(dp[s-5]+v[n])<<endl;    }            return 0;}