首页 > 代码库 > HDU 2546 饭卡

HDU 2546 饭卡

2024-07-16 15:37:16   213人阅读

题目链接：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;}

 

　　　　


联系
我们