砝碼稱重藍橋杯

砝碼稱重藍橋杯是藍橋杯比賽中常見的題型之一，題目描述如下:

有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;
} 

三、總結

砝碼稱重問題是一類比較常見的算法問題，也是藍橋杯比賽中常見的題型之一。本文提供了兩種解題思路：暴力枚舉和動態規劃。在實際應用中，可以根據數據範圍和需求選擇合適的算法，以達到更好的效果。