题解 | 称砝码

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Scan()
    kindStr := scanner.Text()
    kind, _ := strconv.Atoi(kindStr)
    scanner.Scan()
    weightsStr := strings.Fields(scanner.Text())
    weights := make([]int, kind)
    for idx, _ := range weightsStr {
        weights[idx],_ = strconv.Atoi(weightsStr[idx])
    }
    scanner.Scan()
    countsStr := strings.Fields(scanner.Text())
    counts := make([]int, kind)
    for idx, _ := range countsStr {
        counts[idx],_ = strconv.Atoi(countsStr[idx])
    }
    noZeroKind := uniqueWeights(weights, counts)
    fmt.Print(noZeroKind+1)
}

// uniqueWeights 用于计算可以称出的不同重量的个数
// weights: 每种砝码的重量
// counts: 每种砝码的个数
func uniqueWeights(weights []int, counts []int) int {
	// 使用 map 模拟一个动态规划数组 dp，key 表示当前可以称出的重量
	dp := make(map[int]bool)
	dp[0] = true // 初始状态，表示什么都不放时，重量为 0

	// 遍历每种砝码
	for i := 0; i < len(weights); i++ {
		w := weights[i] // 当前砝码重量
		c := counts[i]  // 当前砝码个数

		// 用于临时存储当前砝码可能组合出来的新重量
		cur := make(map[int]bool)

		// 遍历当前所有已知的可达重量
		for weight := range dp {
			// 尝试放 1 到 c 个当前砝码
			for k := 1; k <= c; k++ {
				newWeight := weight + w*k
				cur[newWeight] = true // 将新重量加入当前回合
			}
		}

		// 把当前回合新得到的重量合并到 dp 中
		for k := range cur {
			dp[k] = true
		}
	}

	// 删除 0 重量（不放任何砝码）
	delete(dp, 0)

	// 剩下的 key 就是所有不同的正整数重量
	return len(dp)
}