首页 > 代码库 > hdu 2546 饭卡 01背包
hdu 2546 饭卡 01背包
先将前n-1个从小到大排序,对m-5进行01背包,然后答案就是m-dp[m-5]-a[n-1]
至于为什么最后减去最贵的菜品,而不是把最贵的菜品也放到01背包里呢,
因为如果可以把最贵菜品a[n-1]可以放到背包里,那么其他菜品a[i]也一定可以放在背包里(背包的容量为m-5),最后都是减去a[i]+a[n-1],所以可以吧最贵的菜品不放入背包,直接最后减去
#include<iostream> #include<stdio.h> #include<algorithm> using namespace std; #define N 1005 int a[N],dp[N]; int main(){ int n,m; while(cin>>n,n){ for(int i=0;i<n;i++){ scanf("%d",&a[i]); } cin>>m; int s=m-5; if(s<0){ printf("%d\n",m); continue; } sort(a,a+n); for(int i=0;i<=m;i++) dp[i]=0; for(int i=0;i<n-1;i++){ for(int j=s;j>=a[i];j--) dp[j]=max(dp[j-a[i]]+a[i],dp[j]); } printf("%d\n",m-dp[s]-a[n-1]); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。