wikioi-天梯-提高一等-哈希表-2144：砝碼稱重2

題目描述 Description

有n個砝碼，現在要稱一個品質為m的物體，請問最少需要挑出幾個砝碼來稱？

注意一個砝碼最多隻能挑一次

輸入描述 Input Description

第一行兩個整數n和m，接下來n行每行一個整數表示每個砝碼的重量。

輸出描述 Output Description

輸出選擇的砝碼的總數k，你的程式必須使得k盡量的小。

樣例輸入 Sample Input

3 10

5

9

1

樣例輸出 Sample Output

2

資料範圍及提示 Data Size & Hint

1<=n<=30，1<=m<=2^31，1<=每個砝碼的品質<=2^30

類型：其他  難度：2

題意：給出n個數，要求從中挑出k個數，使它們的和為m，求最小的k

分析：一個簡單的思路：

1、就是把n個數分成兩份，分别求每份的數所有可能取的和，用cnt1和cnt2兩個哈希表記錄，其中cnt1[i]=j表示最少需要湊出和為i，至少需要j個數。

周遊方法可以用二進制表示每個數是否取，比如有5個數，那麼周遊1 - (2^5-1)，每個數二進制為1，則将這個數累加，将累加的和作為哈希表的key，選取的個數作為哈希表的value，若比之前的小或是新出現的則更新哈希表對應項

2、對于兩個哈希表cnt1和cnt2，周遊其中一個哈希表，設目前周遊的項為cnt1[i]=j，那麼找cnt2[m-i]=k是否存在，若存在，那麼j+k即為總共需要取的個數，記錄最小值即為所求

3、最後分别看cnt1[m]和cnt2[m]是否存在，就是單獨取兩部分的和就能構成結果，更新結果為最小值

用stl map實作哈希的功能，比自己寫哈希稍微慢了點，不過夠用了。

本來嘗試用stl hash_map實作，但是hash_map不是ansi c的标準，我用的編譯器要加using namespace __gnu_cxx，并且wikioi的編譯器不認，就沒有用。

代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
using namespace std;

map<long long,int> cnt1,cnt2;

int main()
{
    int n;
    long long m;
    vector<int> da;
    scanf("%d%lld",&n,&m);
    
    for(int i=0; i<n; i++)
    {
        int tmp;
        scanf("%d",&tmp);
        da.push_back(tmp);
    }
    sort(da.begin(),da.end());
    
    int l1 = da.size()/2;
    int l2 = da.size() - l1;
    
    for(int i=1; i<1<<l1; i++)
    {
        long long sum=0;
        int tc = 0;
        for(int j=i,k=0; j; j>>=1,k++)
            if(j&1)
            {
                sum += (long long)da[k];
                tc++;
            }
        
        int now = cnt1[sum];
        if(!now || tc<now) cnt1[sum] = tc;
    }
    for(int i=1; i<1<<l2; i++)
    {
        long long sum=0;
        int tc = 0;
        for(int j=i,k=l1; j; j>>=1,k++)
            if(j&1)
            {
                sum += (long long)da[k];
                tc++;
            }
        
        int now = cnt2[sum];
        if(!now || tc<now) cnt2[sum] = tc;
    }
    
    int ans = 50;
    
    map<long long,int>::iterator it;
    for(it=cnt1.begin(); it!= cnt1.end(); it++)
    {
        long long left = m-it->first;
        int tmp = it->second;
        
        if(left > 0)
        {
            int tmp2 = cnt2[left];
            if(tmp2)
            {
                tmp += tmp2;
                ans = min(ans,tmp);
            }
        }
    }
    int r1 = cnt1[m];
    int r2 = cnt2[m];
    if(r1) ans = min(ans,r1);
    if(r2) ans = min(ans,r2);
    printf("%d\n",ans);
}