砝码称重蓝桥杯

砝码称重蓝桥杯是蓝桥杯比赛中常见的题型之一，题目描述如下:

有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 < n; ++i) cin >> 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 < n; ++i) cin >> 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;
} 

三、总结

砝码称重问题是一类比较常见的算法问题，也是蓝桥杯比赛中常见的题型之一。本文提供了两种解题思路：暴力枚举和动态规划。在实际应用中，可以根据数据范围和需求选择合适的算法，以达到更好的效果。