2026.1.24 作业 - # P1441 砝码称重

题目描述

现有 \(n\) 个砝码，重量分别为 \(a_i\)，在去掉 \(m\) 个砝码后，问最多能称量出多少不同的重量（不包括 \(0\)）。

请注意，砝码只能放在其中一边。

输入格式

第 \(1\) 行为有两个整数 \(n\) 和 \(m\)，用空格分隔。

第 \(2\) 行有 \(n\) 个正整数 \(a_1, a_2, a_3,\ldots , a_n\)，表示每个砝码的重量。

输出格式

仅包括 \(1\) 个整数，为最多能称量出的重量数量。

输入输出样例 #1

输入 #1

3 1
1 2 2

输出 #1

3

说明/提示

【样例说明】

在去掉一个重量为 \(2\) 的砝码后，能称量出 \(1, 2, 3\) 共 \(3\) 种重量。

【数据规模】

对于 \(20\%\) 的数据，\(m=0\)。

对于 \(50\%\) 的数据，\(m\leq 1\)。

对于 \(50\%\) 的数据，\(n\leq 10\)。

对于 \(100\%\) 的数据，\(n\leq 20\)， \(m\leq 4\)，\(m < n\)，\(a_i\leq 100\)。

题解

删除物品 \(i\) ,可以理解为第 \(i\) 个物品，有2种重量： \(w[i]\) 和 \(0\)

#include <iostream>
#define LL long long
using namespace std;
int n,m,w[30],dp[21][2002],sum,Ans;
void dfs(int k,int cnt) {if (k>n && cnt==m) {int ss=0;for (int j=1;j<=sum;j++)if (dp[n][j]) ss++;if (ss>Ans) Ans=ss;return;}if (cnt<m) {for (int j=0;j<=sum;j++) dp[k][j]=dp[k-1][j];dfs(k+1,cnt+1);}if (n-k>=m-cnt) {for (int j=sum;j>=w[k];j--)dp[k][j]=dp[k-1][j]||dp[k-1][j-w[k]];for (int j=0;j<w[k];j++) dp[k][j]=dp[k-1][j];dfs(k+1,cnt);}
}
int main() {cin>>n>>m;for (int i=1;i<=n;i++) cin>>w[i],sum+=w[i];dp[0][0]=1;dfs(1,0);cout<<Ans<<endl;return 0;
}