洛谷 P1441 砝码称重 题解

发表于 | 分类于 | | 热度: ℃

Description

有 $n$ 个砝码，重量为 $a_1, a_2, a_3, …, a_n$。在去掉 $m$ 个砝码后，问最多能称量出多少不同的重量（不包括 $0$ ）。

数据范围：$n<=20, m<=4, m<n, a_i<=100$

Solution

首先想到的是爆搜。先暴力去掉 $m$ 个砝码，然后暴力出能凑出多少种重量。最后答案取 $max$。会 $TLE$ 一些点。

可以使用 $dp$ 对第二步进行优化。设 $f[i]=(0/1)$ 为重量 $i$ 能否被凑出。注意是背包，不要忘记倒着循环。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n, m, ans = 0, cnt = 0, res, f[100000], a[60], d[60];

void dp()
{
    memset(f, 0, sizeof(f)); f[0] = 1; cnt = res = 0;
    for(int i = 1; i <= n; i++)
    {
        if(d[i]) continue;
        for(int j = cnt; j >= 0; j--)
            if(f[j] && !f[j + a[i]]) f[j + a[i]] = 1, res++;
        cnt += a[i];
    }
}

void dfs(int x, int tot)
{
    if(tot == m)
    {
        dp();
        ans = max(ans, res);
        return ;
    }
    if(x == n) return ;
    d[x + 1] = 1;
    dfs(x + 1, tot + 1);
    d[x + 1] = 0;
    dfs(x + 1, tot);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    dfs(0, 0);
    printf("%d", ans);
    return 0;
}