https://www.luogu.org/problemnew/show/P1441

C++版本一

题解：DFS+DP

DFS过程

通过dfs过程，我们的目标是选择出所有的可能情况，然后对这些情况进行dp。

我们有两种选择：

1）从n个数字中选取n-m个数字保留

2）从n个数字中选取m个数字删除

观察题目的数据范围，我们发现，如果我们对dfs过程进行有效性剪枝，那么方案2）的时间复杂度会比方案1）小很多，扩展的状态数量也较小。

由此，我们可以设计出比较优的dfs函数：

void dfs(int cur,int now)//cur代表当前已经选取/放弃了多少个砝码，now代表已经放弃了多少个砝码
{
    if(now>m)return;//如果已经放弃的砝码数超过了需要放弃的砝码数，剪枝
    if(cur==n){if(now==m)dp();return;}//如果搜索完后正好符合条件，执行一次dp过程
    dfs(cur+1,now);//不放弃当前的砝码，继续向下
    tf[cur]=true;//留下足迹
    dfs(cur+1,now+1);//放弃当前砝码
    tf[cur]=false; //擦除足迹
}

DP过程

通过dfs过程找到一种状态以后，求出使用当前留下的这些砝码可以凑出多少个不同的重量，我们通过dp解决这个问题。

观察题目可得，这个过程可以通过01背包实现。

定义f[i][j]为当前选取到了第j个砝码，如果通过之前的砝码可以称量出重量i那么f[i][j]的值为true。

状态转移方程为： f[i][j]=f[i-a[i]][j-1]

初始状态为f[0][j]=true

最后f[i][n]中true的个数就是通过这些砝码可以计算出的重量值。

通过滚动数组，我们可以只定义一个f[i]数组，降低了时间复杂度，注意此时内层循环倒序。

代码：

void dp()//不传参，全部定义在全局变量中
{
    memset(f,0,sizeof f);f[0]=true;ans=0;tot=0;//清零，因为可能要调用多次
    for(int i=0;i<n;i++)//从前到后选取所有的砝码
    {
        if(tf[i])continue;//如果被标记为已经舍弃就跳过
        for(int j=tot;j>=0;j--)if(f[j]&&!f[j+a[i]])f[j+a[i]]=true,ans++;//否则dp并且维护ans的值
        tot+=a[i];//这个tot意为当前f[i]为真值的最大的i，极大加快了dp过程
    }
    ret=max(ans,ret);//更新最后的答案
}
/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
ll ans,cnt,flag,temp,sum;
int a[N];
int dp[N];
bool vis[N];
char str;
void DP(){
    memset(dp,false,sizeof(dp));
    dp[0]=true;
    sum=0;cnt=0;
    for(int i=1;i<=n;i++){
        if(vis[i])
            continue;
        sum+=a[i];
        for(int j=sum;j>=a[i];j--){
            if(!dp[j]&&dp[j-a[i]]){
                dp[j]=true;cnt++;
            }
        }
    }
    return;
}
void dfs(int x,int now){
    
    if(x==m){
        DP();
        ans=max(ans,cnt);//cout<<ans<<endl;
        return;
    }
    if(now>n)
        return;
    dfs(x,now+1);
    vis[now]=1;
    dfs(x+1,now+1);
    vis[now]=0;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%d%d",&n,&m);
    //scanf("%d",&t);
    //while(t--){}
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    dfs(0,1);
    cout<<ans<<endl;
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

题解：bitset

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
ll ans,cnt,flag,temp,sum;
int a[N];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%d%d",&n,&m);
    //scanf("%d",&t);
    //while(t--){}
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i = 0, li = 1 << n; i < li; i++) {
        if(__builtin_popcount(i) == n - m) {
            std::bitset<2010> S;
            S[0] = 1;
            for(int j = 1; j <=n; j++) if(i & (1 << (j-1))) S |= S << a[j];
            int siz = S.count();
            ans = ans > siz ? ans : siz;
        }
    }
    cout<<ans-1<<endl;
    //cout << "Hello world!" << endl;
    return 0;
}