首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。