题解 P1441 【砝码称重】
hsfzLZH1
2017-10-22 18:07:16
此题的解法类似于NOIP2014普及组T4，思路都是先dfs枚举再dp。
### dfs过程
通过dfs过程，我们的目标是选择出所有的可能情况，然后对这些情况进行dp。
我们有两种选择：
1）从n个数字中选取n-m个数字保留
2）从n个数字中选取m个数字删除
观察题目的数据范围，我们发现，如果我们对dfs过程进行有效性剪枝，那么方案2）的时间复杂度会比方案1）小很多，扩展的状态数量也较小。
由此，我们可以设计出比较优的dfs函数：
```cpp
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]数组，降低了时间复杂度，注意此时内层循环倒序。
代码：
```cpp
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);//更新最后的答案
}
```
总代码：
```cpp
#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;
}
```