题解 | #称砝码#

解题思路

这是一个组合问题，需要计算所有可能的砝码重量组合。主要思路如下：

1. 使用集合(Set)存储所有可能的重量组合，初始包含重量0
2. 对于每种砝码：
   • 获取当前已有的所有重量组合
   • 尝试将当前砝码的1到count[i]倍重量加到已有的每个重量上
3. 利用集合的去重特性自动处理重复重量
4. 最终集合的大小即为所有可能的重量组合数量

代码

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> weights(n);
    vector<int> counts(n);
    
    // 输入砝码重量
    for(int i = 0; i < n; i++) {
        cin >> weights[i];
    }
    // 输入砝码数量
    for(int i = 0; i < n; i++) {
        cin >> counts[i];
    }
    
    unordered_set<int> possible_weights{0};  // 初始包含重量0
    
    // 遍历每种砝码
    for(int i = 0; i < n; i++) {
        vector<int> current_weights(possible_weights.begin(), possible_weights.end());
        // 尝试添加1到count[i]个当前砝码
        for(int j = 1; j <= counts[i]; j++) {
            for(int weight : current_weights) {
                possible_weights.insert(weight + weights[i] * j);
            }
        }
    }
    
    cout << possible_weights.size() << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] weights = new int[n];
        int[] counts = new int[n];
        
        // 输入砝码重量
        for(int i = 0; i < n; i++) {
            weights[i] = sc.nextInt();
        }
        // 输入砝码数量
        for(int i = 0; i < n; i++) {
            counts[i] = sc.nextInt();
        }
        
        Set<Integer> possible_weights = new HashSet<>();
        possible_weights.add(0);  // 初始包含重量0
        
        // 遍历每种砝码
        for(int i = 0; i < n; i++) {
            List<Integer> current_weights = new ArrayList<>(possible_weights);
            // 尝试添加1到count[i]个当前砝码
            for(int j = 1; j <= counts[i]; j++) {
                for(int weight : current_weights) {
                    possible_weights.add(weight + weights[i] * j);
                }
            }
        }
        
        System.out.println(possible_weights.size());
    }
}

def get_weight_combinations():
    n = int(input())  # 砝码种数
    weights = list(map(int, input().split()))  # 每种砝码的重量
    counts = list(map(int, input().split()))   # 每种砝码的数量
    
    # 使用集合存储所有可能的重量组合
    possible_weights = {0}  # 初始包含重量0
    
    # 遍历每种砝码
    for i in range(n):
        current_weights = list(possible_weights)
        # 对于当前砝码，尝试添加1到count[i]个
        for j in range(1, counts[i] + 1):
            # 将当前砝码的j倍重量加到已有重量组合中
            for weight in current_weights:
                possible_weights.add(weight + weights[i] * j)
    
    return len(possible_weights)

# 输出结果
print(get_weight_combinations())

算法及复杂度

• 算法：集合枚举
• 时间复杂度：，其中 为砝码种数， 为每种砝码的最大数量， 为可能的重量组合数
• 空间复杂度：，其中 为可能的重量组合数