@[无叶科夫](/user/129926)
（1）如果a[i]为0，DP过程中跳过即可，不必枚举，提高效率，因为a[i]为零表示该砝码无效。（2）bitset改成整数数据记录，可以提高效率。
AC代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
template <class T> void re(T &x);
int n,m,sum,ans;
int a[23];
int ta[23];
int f[2005];
void bag()
{
int curans(0);
memset(f, 0, sizeof f);
f[0]=1;
for(int i=1;i<=n;++i)
{
if (a[i] == 0) continue;
for(int j=sum;j>=a[i];--j)
{
f[j]=f[j]|f[j-a[i]];
}
}
for(int i=1;i<=sum;++i)
if(f[i])++curans;
ans=max(ans,curans);
return;
}
void dfs(int c,int k)
{
if(k==0)
{
bag();
return;
}
for(int i=c+1;i<=n;++i)
{
sum-=a[i];
a[i]=0;
dfs(i,k-1);
a[i]=ta[i];
sum+=a[i];
}
return;
}
int main()
{
re(n);re(m);
for(int i=1;i<=n;++i)
{
re(a[i]);
sum+=a[i];
ta[i]=a[i];
}
dfs(0,m);
cout<<ans;
return 0;
}
template <class T> void re(T &x)
{
x=0;bool f=0;char ch=getchar();
while(ch<'0'||ch>'9')
{f|=(ch=='-');ch=getchar();}
while(ch>='0'&&ch<='9')
{x=x*10+ch-48;ch=getchar();}
if(f)x=-x;
}
```
by metaphysis @ 2020-11-23 19:58:39
@[metaphysis](/user/333388) %%%
by 无叶科夫 @ 2020-11-23 21:04:52
```cpp
@metaphysi
#include<stdio.h>
#define N 20
#define max 100
int arr[N];
int set_[N];
int n, m, maxsum;
template <class T> void re(T& x)
{
x = 0; bool f = 0; char ch = getchar();
while (ch < '0' || ch>'9')
{
f |= (ch == '-'); ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - 48; ch = getchar();
}
if (f)x = -x;
}
void DFS(int k)
{
if (k < m)
{
for (int i = 0; i < n; i++)
{
if (set_[i])
{
set_[i] = 0;
DFS(k + 1);
set_[i] = 1;
}
}
}
else
{
int dp[N * max] = { 0 };
int sum = 0;
int max_ = 0;
dp[0] = 1;
for (int i = 0; i < n; i++)
{
if (set_[i]) {
sum += arr[i];
for (int j = sum; j >= arr[i]; j--)
{
dp[j] = dp[j]|dp[j - arr[i]];
}
}
}
for (int i = 1; i <= sum; i++)
if (dp[i])
max_++;
if (max_ > maxsum)
maxsum = max_;
}
}
int main()
{
re(n), re(m);
maxsum = 0;
for (int i = 0; i < n; i++) {
re(arr[i]);
set_[i] = 1;
}
DFS(0);
printf("%d\n", maxsum);
return 0;
}
```
by 123456xyzMMM @ 2022-09-20 16:21:59
@[metaphysis](/user/333388) 大佬为什么我感觉我运行次数还少一点，但是过不了
by 123456xyzMMM @ 2022-09-20 16:23:03
@[123456xyzMMM](/user/679814)
您 DFS 过程生成的是 $n$ 种物品去掉 $m$ 种物品后的排列，而不是生成 $n$ 种物品去掉 $m$ 种物品后的组合，当然复杂度很高。
by metaphysis @ 2022-09-20 21:46:36