CODEVS_2144 砝码称重 2 折半搜索+二分查找+哈希-白红宇

CODEVS_2144 砝码称重 2 折半搜索+二分查找+哈希

阅读量：4684 次

发布时间：2019-06-09

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

#include
    
     #include
     
      #include
      
       #include
       #include
        
         #define MAX_N 35#define MAX_T 500005using namespace std;typedef long long ll;map
         
           ma[2];ll n,m,a[MAX_N],tot[2]={0,0};ll d[2][MAX_T];ll ans=MAX_T;void dfs(ll x,ll num,ll sum,int en,int t){ if(sum>m)return; if(ma[t].find(sum)==ma[t].end())ma[t][sum]=tot[t]++; if(d[t][ma[t][sum]]==-1)d[t][ma[t][sum]]=num; else d[t][ma[t][sum]]=min(d[t][ma[t][sum]],num); if(x==en)return; dfs(x+1,num,sum,en,t); dfs(x+1,num+1,sum+a[x],en,t);}int main(){ cin>>n>>m; for(int i=0;i
          
           >a[i]; memset(d,-1,sizeof(d)); dfs(0,0,0,n/2,0); dfs(n/2,0,0,n,1); map
           
            ::iterator it[2]; for(it[0]=ma[0].begin();it[0]!=ma[0].end();it[0]++) { ll tmp=m-(it[0]->first); it[1]=ma[1].find(tmp); if(it[1]!=ma[1].end())ans=min(ans,d[0][it[0]->second]+d[1][it[1]->second]); } cout<
            
             <

原题链接：http://codevs.cn/problem/2144/

题目描述

Description

有n个砝码，现在要称一个质量为m的物体，请问最少需要挑出几个砝码来称？

注意一个砝码最多只能挑一次

输入描述

Input Description

第一行两个整数n和m，接下来n行每行一个整数表示每个砝码的重量。

输出描述

Output Description

输出选择的砝码的总数k，你的程序必须使得k尽量的小。

样例输入

Sample Input

3 10

样例输出

Sample Output

数据范围及提示

Data Size & Hint

1<=n<=30，1<=m<=2^31，1<=每个砝码的质量<=2^30

刚开始做这道题采取了记忆化搜索的办法，但是很容易就超内存超时了。于是考虑将原数列分为两半进行搜索，记录下所有能够组成的sum及其所花的最小元素。由于我用了STL的map来记录所有的sum，所以两边的sum都是有序的，这样从前半的sum就能推出后一半所需的值，利用map可以很容易的进行搜索。

详见代码：

转载于:https://www.cnblogs.com/HarryGuo2012/p/4524046.html

你可能感兴趣的文章