题目链接

题目描述

现有n个砝码,重量分别为a1,a2,a3,……,an,在去掉m个砝码后,问最多能称量出多少不同的重量(不包括0)。

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

## 输入格式
输入文件weight.in的第1行为有两个整数n和m,用空格分隔

第2行有n个正整数a1,a2,a3,……,an,表示每个砝码的重量。

输出格式

输出文件weight.out仅包括1个整数,为最多能称量出的重量数量。

输入输出样例

输入

3 1
1 2 2

输出

3

说明/提示

【样例说明】

在去掉一个重量为2的砝码后,能称量出1,2,3共3种重量。

【数据规模】

对于20%的数据,m=0;

对于50%的数据,m≤1;

对于50%的数据,n≤10;

对于100%的数据,n≤20,m≤4,m<n,ai≤100。

题解

首先枚举取哪几个,然后DP找这种的取法的最多可称量数,与ans比较即可

代码

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

int ans=0, n, m, a[25], arr[25];
bool took[25],dp[100*100+20];

void check()
{
memset(arr, 0, sizeof(arr));
memset(dp, 0, sizeof(dp));
int cnt=0,sum=0;
dp[0]=1;
for (int i=1; i<=n; i++)
if (!took[i])
{
arr[++cnt]=a[i];
sum += a[i];
}
//cout << sum;
for (int i=1; i<=cnt; i++)
for (int j=sum; j>=arr[i]; j--)
{
dp[j]|=dp[j-arr[i]];
}

int tmp=0;

for (int i=1; i<=sum; i++)
tmp+=dp[i];

ans=max(ans,tmp);
}

void dfs(int cnt, int index)
{
if (cnt == 0)
{
check();
return;
}

for (int i=index; i<=n; i++)
{
took[i]=1;
dfs(cnt-1, i+1);
took[i]=0;

}
}

int main()
{
cin >> n >> m;
for (int i=1; i<=n; i++)
cin >> a[i];

dfs(m, 1);

cout << ans;
return 0;
}

评论