描述

$$对于给定的 $n$n 种砝码，重量互不相等，依次为 $m_1,m_2,\dots ,m_n$m1​,m2​,…,mn​ ，数量依次为 $x_1,x_2,\dots ,x_n$x1​,x2​,…,xn​ ，
$$现在要用这些砝码去称物体的重量（放在同一侧），问能称出多少种不同的重量。特别地，称重重量包括 $0$0 。

输入描述：

$$第一行输入一个整数 $n(1\leqq n\leqq 10)$n(1≦n≦10) 代表砝码的个数。
$$第二行输入 $n$n 个整数 $m_1,m_2,\dots ,m_n(1\leqq m_i\leqq 2000)$m1​,m2​,…,mn​(1≦mi​≦2000) 代表每种砝码的重量。
$$第三行输入 $n$n 个整数 $x_1,x_2,\dots ,x_n(1\leqq x_i\leqq 10)$x1​,x2​,…,xn​(1≦xi​≦10) 代表每种砝码的数量。

输出描述：

$$输出一个整数，代表利用给定的砝码可以称出的不同的重量数。

示例1

输入：

2
1 2
2 1

输出：

5

说明：

$$在这个样例中，有 $2$2 个重量为 $1$1 的砝码，$1$1 个重量为 $2$2 的砝码。称重方式如下：
$\bullet$∙不放砝码，称重重量为 $0$0 ；
$\bullet$∙放 $1$1 个重量为 $1$1 的砝码，称重重量为 $1$1 ；
$\bullet$∙放 $2$2 个重量为 $1$1 的砝码，称重重量为 $2$2 ；
$\bullet$∙放 $1$1 个重量为 $1$1 的砝码、$1$1 个重量为 $2$2 的砝码，称重重量为 $3$3 ；
$\bullet$∙放 $2$2 个重量为 $1$1 的砝码、$1$1 个重量为 $2$2 的砝码，称重重量为 $4$4 。
$$因此，能称出的不同重量有 $5$5 种，分别是 $0,1,2,3,4$0,1,2,3,4 。

第一版思路

1. 将所有砝码入栈
2. 通过滑动窗口的方式计算所有砝码的和，去掉重复的

void async function () {
    // Write your code here
    const res = [];
    const num = (await readline());
    const list = (await readline()).split(" ");
    const listNum = (await readline()).split(" ");
    //console.log(listNum);
    for(let i=0; i< num;i++){
        for(let j =0; j<listNum[i]; j++){
            res.push(list[i]*1);
        }
    }
   
    //子序列
    //console.log(res);
    const total = [0];
    const child=()=>{
        //获取不同的组合：放单个砝码，...n个砝码
        for(let i=1;i<=res.length;i++){
            //控制窗口
            for(let j=0;j<res.length;j++){
                const temp = res.slice(j,j+i);
                let sum = 0;
                for(const v of temp){
                    sum += v;
                }
                if(!total.includes(sum)){
                    total.push(sum);
                }
            }
        }
    }
    child();
    console.log(total.length)

}()

另一种方式

void (async function () {
    // Write your code here
   const n = parseInt(await readline());
    const category = (await readline()).split(" ").map(Number);
    const cnt = (await readline()).split(" ").map(Number);
    //序列化砝码，比如两个1g和一个2g的砝码用[1,1,2]表示
    const nums = [];
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < cnt[i]; j++) {
            nums.push(category[i]);
        }
    }
    // 计算种数
    const set = new Set([0]);
    for(let i = 0; i < nums.length; i++){
        let arr = [...set];
        for(const k of arr){
            set.add(k+nums[i]);
        }
    }
    console.log(set.size);
})();

上面的代码有问题，只考虑了砝码放同侧的情况，还需要考虑砝码放对侧的情况。

动态规划

一、二维 DP 表定义

纵向（行 i）

i = 已经处理完前 i 个砝码

• i=0：没有放任何砝码（初始状态）
• i=1：处理完第 1 个砝码（w=1）

横向（列 j）

dp 数组下标，对应真实称重差值 G = j - offset

列 0：G=-1；列 1：G=0；列 2：G=1

dp[i][j] = true：前 i 个砝码能组合出差值 j-offset

2 类砝码，n=2，w=[1,2]，cnt=[1,1]

砝码：1、2 各一个

总重量 totalMax = 3，offset=3

下标 j：0~6，对应 G=-3 ~ +3

列映射：

j0→-3，j1→-2，j2→-1，j3→0，j4→1，j5→2，j6→3

行：

i0：无砝码

i1：处理完砝码 1

i2：处理完砝码 2

完整二维表

表格

i\j	j0(G=-3)	j1(G=-2)	j2(G=-1)	j3(G=0)	j4(G=1)	j5(G=2)	j6(G=3)
i=0	F	F	F	T	F	F	F
i=1	F	F	T	T	T	F	F
i=2	T	T	T	T	T	T	T

推演说明

1. i=0：只有 j3 为 true
2. i=1（加入 w=1）： j3 衍生 j2、j3、j4 为 true
3. i=2（加入 w=2）： 遍历 i=1 所有 true 位置 (j2,j3,j4)，每个分别 ±2 标记 true，填满全部列

统计答案

筛选 j>3（G>0）：j4、j5、j6 → G=1,2,3，共 3 种可称重量。

和普通背包表格对比区别

普通多重背包：每行只做 j+w 单向更新；

本题砝码 DP：每行同时做 j+w、j-w 双向更新，所以表格左右两侧都会被标记为 true