HDU5887 Herbs Gathering(2016青岛网络赛搜索剪枝)-白红宇

HDU5887 Herbs Gathering(2016青岛网络赛搜索剪枝)

阅读量：6957 次

发布时间：2019-06-27

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

背包问题，由于数据大不容易dp，改为剪枝，先按性价比排序，若剩下的背包空间都以最高性价比选时不会比已找到的最优解更好时则剪枝，即

if(val + (LD)pk[d].val / (LD)pk[d].w * (lim - w) + EPS <= ans){

　　return;

}

没想到一发过，0ms

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;typedef long long LL;typedef long double LD;const int N = 108, INF = 0x3F3F3F3F, EPS = 0.4;struct data{ LL w, val; bool operator<(const data &tp)const{ return val * tp.w > tp.val * w; }}pk[N];int n;LL sum[N], sw[N], lim;LL ans;void dfs(int d, LL w, LL val){ if(val > ans){ ans = val; } if(d >= n){ return; } if(val + (LD)pk[d].val / (LD)pk[d].w * (lim - w) + EPS <= ans){ return; } if(w + pk[d].w <= lim){ dfs(d + 1, w + pk[d].w, val + pk[d].val); } dfs(d + 1, w, val);}int main(){ while(~scanf("%d %I64d", &n, &lim)){ for(int i = 0; i < n; i++){ scanf("%I64d %I64d", &pk[i].w, &pk[i].val); } sort(pk, pk + n); ans = 0; sum[n] = 0; sw[n] = 0; dfs(0, 0, 0); printf("%I64d\n", ans); } return 0;}