首页 > 代码库 > HDU 2546 饭卡( 变形01背包)两种思路
HDU 2546 饭卡( 变形01背包)两种思路
中文题:给你n个菜的价格,问m元最少剩下多少。一个条件是:若大于等于5元可以任意刷一次。卡上金额一定要大于5才可以
变形01背包。若整个菜的价值和都小于m则m-sum;
第一种:
dp[j] 用前n-1个物品能否构成j元
变形01背包。若整个菜的价值和都小于m则m-sum;
否则,按升序排序,易证最后用5购买的菜必然是最后一个。先将背包前n-1个放入,看能放入的数据是多少,然后判断m-5后能出现哪些,利用规则替换n物品
#include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define max(a,b) ( (a) > (b) ?(a) : (b) ) #define min(a,b) ( (a) < (b) ?(a) : (b) ) #define maxn 1100 int a[maxn]; int dp[maxn]; int main() { int n; int i,j,m; while(~scanf("%d",&n) && n) { for(i=1;i<=n;i++) scanf("%d",a+i); scanf("%d",&m); if(m<5) {printf("%d\n",m);continue;} sort(a+1,a+1+n); memset(dp,0,sizeof(dp)); dp[0]=1;int ans=0; for(i=1;i<n;i++) for(j=m+50;j>=a[i];j--) if(dp[j-a[i]]) dp[j]=1,ans=max(ans,j); if(ans+a[n]<=m) printf("%d\n",m-a[n]-ans); else { for(i=m;i>=0;i--) if(dp[i]) { if(i<=m-5) {ans=min(ans,m-i-a[n]);break;} else ans=min(ans,i); } printf("%d\n",ans); } } return 0; }
第二种:用m-5充分装菜,最后再用5装n,就可以了
dp[j] 前n-1个物品,用j元最多买多少钱的菜。
#define max(a,b) ( (a) > (b) ?(a) : (b) ) #define min(a,b) ( (a) < (b) ?(a) : (b) ) #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; int main() { int i,j,k; int t,n,m; int maxn; int dp[2014]={0},price[2014]={0}; while(scanf("%d",&n)!=EOF,n) { memset(price,0,sizeof(price)); memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) { cin>>price[i]; } cin>>m; if(m<5) { printf("%d\n",m); continue; } sort(price+1,price+n+1); maxn=price[n]; m=m-5; for(i=1;i<n;i++) { for(j=m;j>=price[i];j--) { dp[j]=max(dp[j],dp[j-price[i]]+price[i]); } } printf("%d\n",m+5-dp[m]-maxn); } return 0; }/*1505101 2 3 2 1 1 2 3 2 150610 30 45 50 25 15111610 30 45 50 25 154*/
HDU 2546 饭卡( 变形01背包)两种思路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。