7行程式碼解決P1441砝碼稱重（附優化過程）
先貼上最終程式碼感受一下：
#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;
}
說實話，能優化到這個地步，我自己都被驚艷到了
