HDU 2546（01背包）-白红宇

HDU 2546（01背包）

阅读量：5248 次

发布时间：2019-06-14

本文共 1233 字，大约阅读时间需要 4 分钟。

http://acm.hdu.edu.cn/showproblem.php?pid=2546

http://blog.csdn.net/xujinsmile/article/details/7969412

首先拿出5元买最贵的东西，那接下来就是背包容量m-5，物品数量n-1 的01背包问题了。

做背包问题一定要明确边界条件再入手，不然很费时间

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;#define MEM(a,b) memset(a,b,sizeof(a))#define pf printf#define sf scanf#define debug printf("!\n")#define INF 8000#define MAX(a,b) a>b?a:b#define blank pf("\n")#define LL long long#define ep 1e-6int dp[INF];int ci[INF];//容量int wi[INF];//价值int n,V,i,j,v,t,sum;void zeroOnePack(int cost,int weight){ for(v = V-5;v>=cost;v--) { dp[v] =MAX(dp[v],dp[v-cost]+weight); }}void completePack(int cost,int weight){ for(v = cost;v<=V;v++) { dp[v] =MAX(dp[v],dp[v-cost]+weight); pf("tt%d %d %d\n",i,v,dp[v]); }}int main(){ int t; while(sf("%d",&n) && n) { MEM(dp,0); MEM(ci,0); MEM(wi,0); for(i = 1;i<=n;i++) { sf("%d",&wi[i]); } sort(wi+1,wi+n+1); sf("%d",&V); int m = wi[n]; if(V<5) { pf("%d\n",V); continue; } else { n--; for(i = 1;i<=n;i++) { zeroOnePack(wi[i],wi[i]); } pf("%d\n",V-m-dp[V-5]); } } return 0;}