砝码称重详解

#include <bits/stdc++.h>
using namespace std;

const int MAX_SUM = 1000;
int w[6010];    // 拆分后物品重量
bool dp[1010];  // dp[j]表示能否凑出重量j

int main() {
    // 6种砝码数量 a1~a6
    int a[6];
    for (int i = 0; i < 6; i++) {
        cin >> a[i];
    }
    // 对应砝码重量
    int weight[6] = {1, 2, 3, 5, 10, 20};
    
    int cnt = 0;
    for (int i = 0; i < 6; i++) {
        int num = a[i];
        int wi = weight[i];
        int k = 1;
        while (num > 0) {
            int take = min(k, num);
            w[++cnt] = take * wi;
            num -= take;
            k *= 2;
        }
    }
    
    dp[0] = true; // 0重量（不取砝码）初始可达
    // 01背包遍历拆分后的每件物品
    for (int i = 1; i <= cnt; i++) {
        int now_w = w[i];
        // 逆序，一维01背包写法，和第二份模板循环方向一致
        for (int j = MAX_SUM; j >= now_w; j--) {
            dp[j] = dp[j] || dp[j - now_w];
        }
    }
    
    // 统计1~1000有多少种可行重量
    int ans = 0;
    for (int j = 1; j <= MAX_SUM; j++) {
        if (dp[j]) ans++;
    }
    cout << "Total=" << ans << endl;
    return 0;
}