HDOJ(HDU).2546 饭卡(DP 01背包)

2019-11-08 01:52:54

字体：大中小

来源：转载

供稿：网友

HDOJ(HDU).2546 饭卡(DP 01背包)

题意分析

首先要对钱数小于5的时候特别处理，直接输出0。若钱数大于5，所有菜按价格排序，背包容量为钱数-5，对除去价格最贵的所有菜做01背包。因为这时候还剩下5块钱，直接买最贵的那个菜，就可以保证剩下来的钱数是最小的。

代码总览

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define nmax 1005using namespace std;int c[nmax],dp[nmax];bool cmp(int a, int b){ return a<b;}int main(){ //freopen("in.txt","r",stdin); int n; while(scanf("%d",&n) && n){ memset(dp,0,sizeof(dp)); for(int i = 1; i<=n; ++i) scanf("%d",&c[i]); sort(c+1,c+1+n,cmp); int m; scanf("%d",&m); int t = m-5; if(m<5) PRintf("%d/n",m); else if(m == 5) printf("%d/n",m-c[n]); else{ for(int i =1; i<=n-1; ++i){ for(int j = t; j>=c[i];--j) dp[j] = max(dp[j],dp[j-c[i]]+c[i]); } printf("%d/n",m-dp[t]-c[n]); } } return 0;}

上一篇：双栈排序练习

下一篇：编译caffe出现错误：make: *** [.build_release/src/caffe/common.o] Error 1