7行代码解决P1441砝码称重（附优化过程）
7行代码解决P1441砝码称重！！内附详细的优化过程，涉及bitset优化DP、大小为k的子集枚举等知识点。
先贴上最终代码感受一下：
#include <bits/stdc++.h>
using namespace std;
int i, N, M, wi[21], res = 0;
int main()
{
cin >> N >> M;
for(i = 1; i <= N; i++)cin >> wi[i];
int S = (1 << (N - M)) - 1; //（1）
while (S < 1 << N) //（2）
{
bitset<2010> f; //（3）
for(i = 1, f[0] = 1; i <= N; i++)if(S & 1 << (i - 1)) f |= f << wi[i]; //（4）
res = max(res, int(f.count())); //（5）
int x = S & -S, y = S + x; //（6）
S = ((S & ~y) / x >> 1) | y; //（7）
}
cout << res - 1;
return 0;
}
它的核心代码只有7行！！（1）~（7）
这段代码在此题最优解排行榜排名第四！！！（附截图，截图时间2021年1月24日，12:03:02）
解决思路为枚举大小为k的子集+bitset优化DP
下面是我的优化过程
题干
P1441 砝码称重
题目描述
现有n个砝码，重量分别为 ai，在去掉 m 个砝码后，问最多能称量出多少不同的重量（不包括 0）。
请注意，砝码只能放在其中一边。
输入格式
第 1 行为有两个整数 n 和 m，用空格分隔。
第 2 行有 n 个正整数a1,a2,a3,…,an，表示每个砝码的重量。
输出格式
仅包括 1 个整数，为最多能称量出的重量数量。
输入输出样例
输入 #1
3 1
1 2 2
输出 #1
3
说明/提示
【样例说明】
在去掉一个重量为 2 的砝码后，能称量出 1, 2, 3 共 3 种重量。
【数据规模】
对于 20% 的数据，m = 0 m = 0。
对于 50% 的数据，m ≤ 1。
对于 50% 的数据，n ≤ 10。
对于 100% 的数据，n ≤ 20， m ≤ 4，m < n，ai ≤ 100。
题目分析
我们不难看出，解决此题要解决两个子问题：
-
找到n个砝码去掉m个砝码的不同方案。
-
对每个方案再求出不同重量的方案数（使用当前方案的砝码可以凑出多少个不同的重量）。
解法一：搜索+DP
用搜索枚举出n个砝码去掉m个砝码的方案（状态），再用DP求不同重量的方案数。
#include <bits/stdc++.h>
#define maxn 2010
using namespace std;
int N, M;//有N个砝码，去掉M个砝码
int wi[maxn];//每个砝码的重量
bool vis[maxn];//每个砝码的状态：false被移除，true未被移除（存在）
int res = 0;//不同重量的最大方案数
bool f[maxn];//dp数组，f[n]表示是否存在一个重量为n的方案
//动态规划求不同重量的方案数
void dp()
{
memset(f, false, sizeof(f));//重置f数组
int ans = 0;//不同重量的方案数
f[0] = true; //存在重量为0的方案（不同的重量不包含0，所以不计入方案数）
int max_w = 0; //存在方案的最大重量
for(int i = 1; i <= N; i++) //选第i个砝码
{
if(!vis[i])continue;//如果第i个砝码被移除就跳过
for(int j = max_w; j >= 0; j--)
{
//如果存在重量为j的方案，那么j+wi[i]的方案也一定存在
if(f[j] && !f[j + wi[i]])
{
f[j + wi[i]] = true;
ans++;//方案数加一
}
}
max_w+=wi[i];//更新最大重量
}
res = max(res, ans);//维护最大方案数
}
//利用搜索算法找N个砝码去掉M个砝码的方案（维护vis数组）
void dfs(int cur, int del) //cur 当前该维护哪个砝码的状态；del 已经移除了几个砝码
{
//搜索剪枝
if(del > M)return; //移除的砝码数大于M
//搜索边界
if(cur == N + 1) //一共有N个砝码，处理第N+1个砝码时到达搜索边界
{
if(del == M) //如果恰好删除了M个，即找到N个砝码去掉M个砝码的一个方案
{
dp();//维护这个方案下，不同重量的最大方案数（维护res）
}
return;
}
//分支1：不移除当前砝码
dfs(cur + 1, del); //直接维护第cur+1个砝码，因为没有移除操作，del不变
//分支2：移除当前砝码
vis[cur] = false; //移除当前砝码
dfs(cur + 1, del + 1);
vis[cur] = true; //回溯时将移除的砝码重新加回去
}
int main()
{
cin >> N >> M;
for(int i = 1; i <= N; i++)cin >> wi[i];//输入每个砝码重量
memset(vis, true, sizeof(vis));//初始化vis数组
dfs(1, 0);//初始搜索的状态
cout << res;
return 0;
}
解法二：子集枚举+DP
用“集合”的子集枚举方法枚举状态，然后用popcount判断是否每个状态是否满足条件，对满足条件的状态用DP求不同重量的方案数。
#include <bits/stdc++.h>
#define maxn 2010
using namespace std;
int N, M;//有N个砝码，去掉M个砝码
int wi[maxn];//每个砝码的重量
int res = 0;//不同重量的最大方案数
bool f[maxn];//dp数组，f[n]表示是否存在一个重量为n的方案
//动态规划求不同重量的方案数
void dp(int S)//“集合”S
{
memset(f, false, sizeof(f));//重置f数组
int ans = 0;//不同重量的方案数
f[0] = true; //存在重量为0的方案（不同的重量不包含0，所以不计入方案数）
int max_w = 0; //存在方案的最大重量
for(int i = 1; i <= N; i++) //选第i个砝码
{
if(S & 1 << (i - 1))//利用位运算判断第i个元素（砝码）是否在“集合”内
{
for(int j = max_w; j >= 0; j--)
{
//如果存在重量为j的方案，那么j+wi[i]的方案也一定存在
if(f[j] && !f[j + wi[i]])
{
f[j + wi[i]] = true;
ans++;//方案数加一
}
}
max_w += wi[i]; //更新最大重量
}
}
res = max(res, ans);//维护最大方案数
}
//统计二进制中1的个数
int popcount(int S)//“集合”S
{
int ans = 0;//ans为S的二进制中，二进制位为1的个数
while (S)
{
if (S & 1)
{
ans++;
}
S >>= 1;
}
return ans;
}
void subset()//“集合”子集枚举
{
//（1 << N ）- 1的二进制有N位且都为1
//S的每个二进制位代表一个元素，即代表一个砝码
//二进制位为1表示该元素在“集合”内
//二进制位为0表示该元素不在“集合”内
for(int S = 0; S <= (1 << N ) - 1; S++) //N个元素的“集合”的子集枚举
{
if(popcount(S) == N - M)//当“集合”S中有N-M个元素（S的二进制中有N-M个1）
{
dp(S);//根据“集合”S的状态维护最大方案数
}
}
}
int main()
{
cin >> N >> M;
for(int i = 1; i <= N; i++)cin >> wi[i];//输入每个砝码重量
subset();
cout << res;
return 0;
}
解法二优化：大小为k的子集枚举+DP
优化解法二的子集枚举部分，直接枚举大小为k的子集，再对每个子集DP求不同重量的方案数。
直接套用枚举大小为k的子集的模板代码：
int comb = (1 << k) - 1;
while (comb < 1 << n) {
//进行针对组合的处理
int x = comb & -comb, y = comb + x;
comb = ((comb&~y) / x >> 1) | y;
}
套用后对应的代码：
int S = (1 << (N - M)) - 1;
while (S < 1 << N)
{
dp(S);//根据“集合”S的状态维护最大方案数
int x = S & -S, y = S + x;
S = ((S & ~y) / x >> 1) | y;
}
关于如何枚举大小为k的子集，在我的另一篇博客有详细的讲解，在这里就不详细展开了。
有兴趣的小伙伴可以看一下我的这篇博客：关于“枚举{0,1,…,n-1}所包含的所有大小为k的子集”的理解
完整代码：
#include <bits/stdc++.h>
#define maxn 2010
using namespace std;
int N, M;//有N个砝码，去掉M个砝码
int wi[maxn];//每个砝码的重量
int res = 0;//不同重量的最大方案数
bool f[maxn];//dp数组，f[n]表示是否存在一个重量为n的方案
//动态规划求不同重量的方案数
void dp(int S)//“集合”S
{
memset(f, false, sizeof(f));//重置f数组
int ans = 0;//不同重量的方案数
f[0] = true; //存在重量为0的方案（不同的重量不包含0，所以不计入方案数）
int max_w = 0; //存在方案的最大重量
for(int i = 1; i <= N; i++) //选第i个砝码
{
if(S & 1 << (i - 1))//利用位运算判断第i个元素（砝码）是否在“集合”内
{
for(int j = max_w; j >= 0; j--)
{
//如果存在重量为j的方案，那么j+wi[i]的方案也一定存在
if(f[j] && !f[j + wi[i]])
{
f[j + wi[i]] = true;
ans++;//方案数加一
}
}
max_w += wi[i]; //更新最大重量
}
}
res = max(res, ans);//维护最大方案数
}
void k_subset()//“集合”大小为k的子集枚举
{
//对“集合”S进行大小为N-M的子集枚举
int S = (1 << (N - M)) - 1;
while (S < 1 << N)
{
dp(S);//根据“集合”S的状态维护最大方案数
int x = S & -S, y = S + x;
S = ((S & ~y) / x >> 1) | y;
}
}
int main()
{
cin >> N >> M;
for(int i = 1; i <= N; i++)cin >> wi[i];//输入每个砝码重量
k_subset();
cout << res;
return 0;
}
继续优化解法二：大小为k的子集枚举+bitset优化DP
利用bitset优化DP部分，其他部分不变。
#include <bits/stdc++.h>
#define maxn 2010
using namespace std;
int N, M;//有N个砝码，去掉M个砝码
int wi[maxn];//每个砝码的重量
int res = 0;//不同重量的最大方案数
//动态规划求不同重量的方案数
void dp(int S)//“集合”S
{
int ans;//不同重量的方案数
bitset<maxn> f;
f[0] = 1;
for(int i = 1; i <= N; i++) //选第i个砝码
{
if(S & 1 << (i - 1))//利用位运算判断第i个元素（砝码）是否在“集合”内
{
f |= f << wi[i];//bitset优化的核心代码
}
}
ans = f.count();
res = max(res, ans);//维护最大方案数
}
void k_subset()//“集合”大小为k的子集枚举
{
//对“集合”S进行大小为N-M的子集枚举
int S = (1 << (N - M)) - 1;
while (S < 1 << N)
{
dp(S);//根据“集合”S的状态维护最大方案数
int x = S & -S, y = S + x;
S = ((S & ~y) / x >> 1) | y;
}
}
int main()
{
cin >> N >> M;
for(int i = 1; i <= N; i++)cin >> wi[i];//输入每个砝码重量
k_subset();
cout << res - 1;//重量为0不作为一个方案，所以要减一
return 0;
}
最终代码
去掉注释再稍微调整一下结构就得到了最终代码：
#include <bits/stdc++.h>
using namespace std;
int i, N, M, wi[21], res = 0;
int main()
{
cin >> N >> M;
for(i = 1; i <= N; i++)cin >> wi[i];
int S = (1 << (N - M)) - 1;
while (S < 1 << N)
{
bitset<2010> f;
for(i = 1, f[0] = 1; i <= N; i++)if(S & 1 << (i - 1)) f |= f << wi[i];
res = max(res, int(f.count()));
int x = S & -S, y = S + x;
S = ((S & ~y) / x >> 1) | y;
}
cout << res - 1;
return 0;
}
说实话，能优化到这个地步，我自己都被惊艳到了
版权声明：本文为JihuiPeng原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。