砝码称重蓝桥杯是蓝桥杯比赛中常见的题型之一，题目描述如下:
有M个砝码，重量分别为m1,m2,m3,......,mm；现在需要用这些砝码去称量物体，其中每种砝码的数量没有限制，问能称出多少种不同的物体重量。
一、砝码称重问题的基本思路
要解决这道题，我们需要解决以下两个问题:
1. 如何枚举出所有可能的物体重量
我们可以用背包模型的思路来解决这个问题:
对于每一个砝码，我们有两种选择：要么使用它，要么不使用它。于是，我们可以得到以下的背包转移方程: dp[i] = dp[i] || dp[i-m[j]] 其中，dp[i]表示能否用砝码组成重量为i的物体，m[j]表示第j个砝码的重量。
这个转移方程的意义很简单，对于每一个重量i，我们枚举所有的砝码，计算将其加入或不加入的情况下，能否表示出重量i。
2. 统计不同的物体重量
我们需要用一个哈希表来统计不同的物体重量。在枚举每个重量i时，如果在哈希表中没有重量为i的物体，则将其加入哈希表。
二、代码示例
1. 暴力枚举
int m[N];
bool v[N * M]; //标记重量是否可表示
unordered_map mp; //用哈希表存储所有不同的物体重量，key为物体重量，value为数量
void dfs(int i, int sum, int n) {
if (i == n) { //已经枚举完所有的砝码
if (!v[sum]) { //如果这个重量还没有被标记过
v[sum] = true; //标记这个重量可表示
mp[sum]++; //将这个重量加入哈希表中
}
return;
}
dfs(i + 1, sum + m[i], n); //选择使用第i个砝码
dfs(i + 1, sum, n); //选择不使用第i个砝码
}
int main() {
int n, ans = 0;
cin >> n;
for (int i = 0; i > m[i];
dfs(0, 0, n);
for (auto p : mp) ans++; //统计不同的物体重量
cout << ans << endl;
return 0;
}
2. 动态规划
int m[N];
bool dp[N * M]; //dp[i]表示能否用砝码组成重量为i的物体
int ans = 0;
int main() {
int n;
cin >> n;
for (int i = 0; i > m[i];
dp[0] = true; //重量为0的物体一定可以用0个砝码表示
for (int i = 0; i < n; ++i) { //枚举每个砝码
for (int j = m[i]; j <= 10000; ++j) { //枚举可能的重量
dp[j] = dp[j] || dp[j-m[i]]; //转移方程
}
}
for (int i = 1; i <= 10000; ++i) { //统计不同的物体重量
if (dp[i]) ans++;
}
cout << ans << endl;
return 0;
}
三、总结
砝码称重问题是一类比较常见的算法问题，也是蓝桥杯比赛中常见的题型之一。本文提供了两种解题思路：暴力枚举和动态规划。在实际应用中，可以根据数据范围和需求选择合适的算法，以达到更好的效果。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/248304.html
微信扫一扫 
支付宝扫一扫 