P1441 砝码称重【搜索+01背包】

题目描述

现有n个砝码，重量分别为 $a_iai，在去掉 mm 个砝码后，问最多能称量出多少不同的重量（不包括 00）。$

请注意，砝码只能放在其中一边。

输入格式

第

第 $a_1, a_2, a_3,ldots , a_na1,a2,a3,…,an，表示每个砝码的重量。$

输出格式

仅包括

输入输出样例

输入 #1

3 1
1 2 2

输出 #1

思路

　　搜索出抛弃个数为m的所有组合，在dfs的过程中给不用的砝码打上标记，然后利用01背包的方式求解最大的不同数字的组合即可。

　　这题不加优化，稳妥一点从5000种枚举到0，跑了将近700ms，如果随时记录可用砝码重量的最大值来优化这个过程，就像题解中那样，只要跑100ms左右。

CODE

#include <bits/stdc++.h>
#define dbg(x) cout << #x << "=" << x << endl
#define eps 1e-8
#define pi acos(-1.0)

using namespace std;
typedef long long LL;

const int inf = 0x3f3f3f3f;

template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}

namespace _buff {
    const size_t BUFF = 1 << 19;
    char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
    char getc() {
        if (ib == ie) {
            ib = ibuf;
            ie = ibuf + fread(ibuf, 1, BUFF, stdin);
        }
        return ib == ie ? -1 : *ib++;
    }
}

int qread() {
    using namespace _buff;
    int ret = 0;
    bool pos = true;
    char c = getc();
    for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
        assert(~c);
    }
    if (c == '-') {
        pos = false;
        c = getc();
    }
    for (; c >= '0' && c <= '9'; c = getc()) {
        ret = (ret << 3) + (ret << 1) + (c ^ 48);
    }
    return pos ? ret : -ret;
}

int n, m;
int a[50];
bool vis[50];
int f[50];
int maxx = 0;
int maxn = 0;

int check() {
    int num = 0, f[20007] = {0};
    f[0] = 1;
    for ( int i = 1; i <= n; ++i ) {
        if(vis[i])
            continue;
        for ( int j = maxx; j >= 0; --j ) {
            if(f[j]) {
                f[j + a[i]] = 1;
            }
        }
    }
    for ( int i = 1; i <= maxx; ++i ) {
        if(f[i]) {
            ++num;
        }
    }
    return num;
}

void dfs(int id, int sum) {
    if(check() <= maxn) {
        return;
    }
    if(sum == m + 1) {
        int k = check();
        maxn = max(maxn, k);
        return;
    }
    for ( int i = id + 1; i <= n; ++i ) {
        vis[i] = 1;
        maxx -= a[i];
        dfs(i, sum + 1);
        vis[i] = 0;
        maxx += a[i];
    }
}

int main()
{
    read(n);
    read(m);
    for ( int i = 1; i <= n; ++i ) {
        read(a[i]);
        maxx += a[i];
    }
    sort(a + 1, a + n + 1);
    dfs(0, 1);
    cout << maxn << endl;
    return 0;
}