题解 P1441 【砝码称重】

此题的解法类似于NOIP2014普及组T4，思路都是先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);//更新最后的答案
}

总代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=22;
const int maxm=2010;
int n,m,a[maxn],ans,tot,ret;
bool tf[maxn],f[maxm];
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++;
        tot+=a[i];
    }
    ret=max(ans,ret);
}
void dfs(int cur,int now)
{
    if(now>m)return;
    if(cur==n){if(now==m)dp();return;}
    dfs(cur+1,now);
    tf[cur]=true;
    dfs(cur+1,now+1);
    tf[cur]=false; 
} 
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)scanf("%d",a+i);
    dfs(0,0);
    printf("%d\n",ret);
    return 0;
}