首页 > 试题广场 >

称砝码

[编程题]称砝码

热度指数：213041 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输入描述:

第一行输入一个整数  代表砝码的个数。
第二行输入  个整数  代表每种砝码的重量。
第三行输入  个整数  代表每种砝码的数量。

输出描述:

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

示例1

输入

2
1 2
2 1

输出

说明

在这个样例中，有  个重量为  的砝码， 个重量为  的砝码。称重方式如下：
不放砝码，称重重量为  ；
放  个重量为  的砝码，称重重量为  ；
放  个重量为  的砝码，称重重量为  ；
放  个重量为  的砝码、 个重量为  的砝码，称重重量为  ；
放  个重量为  的砝码、 个重量为  的砝码，称重重量为  。
因此，能称出的不同重量有  种，分别是  。

算法知识视频讲解

Java

hjj123

根据deepseek给出的核心代码优化出来，运行时间113ms

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        int[] weight = new int[count];
        int[] size = new int[count];

        for (int i = 0; i < count; i++) {
            weight[i] = in.nextInt();
        }
        int sumCount = 0;
        for (int i = 0; i < count; i++) {
            size[i] = in.nextInt();
            sumCount += size[i];
        }

        int[] weights = new int[sumCount];
        int maxSum = 0;
        int p = 0;
        for (int i = 0; i < count; i++) {
            for (int j = 0; j < size[i]; j++) {
                weights[p++] = weight[i];
                maxSum += weight[i];
            }
        }

        boolean[] dp = new boolean[maxSum + 1];
        dp[0] = true;

        HashSet<Integer> set = new HashSet<>();
        set.add(0);

        for (int num : weights) {
            for (int j = maxSum; j >= num; j--) {
                if (dp[j - num]) {
                    dp[j] = true;
                    set.add(j);
                }
            }
        }
        System.out.println(set.size());
    }
}

发表于 2025-06-30 20:31:55 回复(0)

Java

morisan

想了好半天，突然就开窍了，关键在于每次选择砝码时，和之前的每轮选砝码的所有结果进行一一组合，需要两个HashSet倒腾数据。

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        if (in.hasNextInt()) { // 注意 while 处理多个 case
            // n种砝码
            int n = in.nextInt();
            // 记录砝码重量
            int[] arr1 = new int[n];
            // 记录各砝码数量
            int[] arr2 = new int[n];

            for (int i = 0; i < n; i++) {
                arr1[i] = in.nextInt();
            }

            for (int i = 0; i < n; i++) {
                arr2[i] = in.nextInt();
            }

            // 用来存储每次选择某个砝码的个数时，和之前所有砝码重量产生的组合
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < n; i ++) {
                Set<Integer> subSet = new HashSet<>();

                for (int j = 0; j <= arr2[i]; j++) {
                    int a = arr1[i] * j;
                    if (set.isEmpty()) {
                        // 第一轮，没有旧数据
                        subSet.add(a);
                    } else {
                        // 之后的数据需要和之前产生的每个结果进行组合
                        for (Integer is : set) {
                            subSet.add(is + a);
                        }
                    }
                }
                set.addAll(subSet);
            }
            System.out.println(set.size());
        }
    }
}

发表于 2025-06-01 23:22:02 回复(0)

Java

牛客763946027号

示例给的输入和实际测试用例的格式不一样

发表于 2025-04-23 12:52:40 回复(0)

Java

牛客430757235号

import java.util.ArrayList;

import java.util.HashSet;

import java.util.Set;

import java.util.List;

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

int n = in.nextInt();

int[] a = new int[n];

int[] b = new int[n];

for(int i = 0;i<n;i++){

a[i] = in.nextInt();

}

for(int i = 0;i<n;i++){

b[i] = in.nextInt();

}

Set<Integer> result = new HashSet<>();//存放结果

result.add(0);

for(int i = 0;i<n;i++){

Set<Integer> temp = new HashSet<>();//存放结果

for(int j = 0;j<=b[i];j++){

for(Integer k:result){

temp.add(k+a[i]*j);

}

result = temp;

}

System.out.println(result.size());

}

发表于 2025-03-24 19:06:08 回复(0)

Java

牛客160935469号

原来是我想得太复杂了，我们可以把这个问题拆解到每一次称出的重量，然后再汇总起来

import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] weights = new int[n];
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            weights[i] = in.nextInt();
        }
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        in.close();
        HashSet<Integer> set = new HashSet<>(); // 存储所有重量的可能结果，去重
        set.add(0);
        for (int i = 0; i < n; i++) {
            HashSet<Integer> onceAdd = new HashSet<>(); // 本次要添加的重量
            for (int j = 1; j <= nums[i]; j++) {
                onceAdd.add(j * weights[i]); // 一种砝码的倍数
                for (Integer v : set) {
                    onceAdd.add(v + weights[i] * j); // 之前计算过的重量要加上新砝码
                }
            }
            set.addAll(onceAdd);
        }
        System.out.println(set.size());
    }
}

发表于 2024-10-01 15:23:38 回复(0)

Java

牛客168205818号

使用前缀和和动态规划的方法来计算可以称出的不同重量。在利用一个布尔数组来记录能达到的重量。

import java.util.Scanner;

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

// 输入砝码种类数

int n = scanner.nextInt();

int[] weights = new int[n];

int[] quantities = new int[n];

// 输入砝码重量

for (int i = 0; i < n; i++) {

weights[i] = scanner.nextInt();

}

// 输入砝码数量

for (int i = 0; i < n; i++) {

quantities[i] = scanner.nextInt();

}

// 计算并输出结果

int result = countWeights(n, weights, quantities);

System.out.println(result);

}

public static int countWeights(int n, int[] weights, int[] quantities) {

int maxWeight = 0;

// 计算最大可能重量

for (int i = 0; i < n; i++) {

maxWeight += weights[i] * quantities[i];

}

boolean[] dp = new boolean[maxWeight + 1];

dp[0] = true; // 可以称出重量0

// 动态规划更新

for (int i = 0; i < n; i++) {

int weight = weights[i];

int quantity = quantities[i];

for (int q = 0; q < quantity; q++) {

for (int j = maxWeight; j >= weight; j--) {

if (dp[j - weight]) {

dp[j] = true;

}

// 统计可以称出的不同重量

int count = 0;

for (boolean b : dp) {

if (b) count++;

}

return count;

}

发表于 2024-09-21 21:50:16 回复(1)

Java

牛客201673936号

import java.util.*;
import java.util.concurrent.CopyOnWriteArraySet;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
          Scanner in = new Scanner(System.in);
                // 注意 hasNext 和 hasNextLine 的区别
                while (in.hasNext()) { // 注意 while 处理多个 case
                    int n = in.nextInt();
                    // 读取砝码的种类
                    int[] weight = new int[n];
                    for (int i = 0; i < n; i++) {
                        weight[i] = in.nextInt();
                    }
                    // 读取砝码的数量
                    List<Integer> list = new ArrayList<>();
                    for (int i = 0; i < n; i++) {
                        int s = 1 ;
                        for (int count = in.nextInt(); count > 0; ) {
                            // 整合到同一个序列当中
                            list.add(weight[i] *(Math.min(s, count)));
                            count -= s;
                            s = s<<1;
                        }
                    }
                    // 创建一个集合Set
                    Set<Integer> set = new CopyOnWriteArraySet<>();
                    // 初始化向集合中添加0
                    set.add(0);
                    // 遍历序列list
                    for (int i : list) {
                        // 遍历集合Set，对每个Set当中的值加值后，添加到Set当中
                        for (int k : set) {
                            set.add(i + k);
                        }
                        set.add(i);
                    }
                    // 统计Set当中的数量，并输出
                    System.out.println(set.size());
                }
    }
}

发表于 2024-09-08 14:06:37 回复(0)

Java

ttkku

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int cnt = in.nextInt();

in.nextLine(); // consume newline

String[] weight = in.nextLine().split(" ");

String[] number = in.nextLine().split(" ");

HashSet<Integer> set = new HashSet<>();

set.add(0); // 初始化集合

for (int i = 0; i < weight.length; i++) {

int val = Integer.parseInt(weight[i]);

HashSet<Integer> tempSet = new HashSet<>();

for (int j = 0; j < Integer.parseInt(number[i]); j++) {

// 对于每一个数量，复制当前的set并更新

tempSet.addAll(set);

for (Integer existingWeight : tempSet) {

set.add(existingWeight + val);

}

System.out.println(set.size());

}

发表于 2024-09-07 16:44:59 回复(0)

Java

爱吃香菜的小确幸在投简历

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int num = in.nextInt();
            int[] typeHeight = new int[num];
            int[] numHeight = new int[num];
            for (int i = 0; i < num; i++) {
                typeHeight[i] = in.nextInt();
            }
            for (int i = 0; i < num; i++) {
                numHeight[i] = in.nextInt();
            }
            HashSet<Integer> hashSet = new HashSet<>();

            hashSet.add(0);
            //遍历所有砝码
            for (int i = 0; i < num; i++) {
                //得到每种砝码的重量和数量
                int weight = typeHeight[i];
                int number = numHeight[i];
                HashSet<Integer> temp = new HashSet<>();
                for (int j = 1; j <= number; j++) {
                    //将当前同种类砝码进行叠加，每次叠加都与之前所称重量数进行对比，有新的就加入到集合中
                    for (Integer w : hashSet) {
                        temp.add(w + weight * j);
                    }
                }
                hashSet.addAll(temp);
            }
            System.out.println(hashSet.size());
        }
    }
}

发表于 2024-07-06 10:46:08 回复(0)

Java

大胆的哈士奇要暴富

import java.util.ArrayList;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Map;

import java.util.Scanner;

import java.util.Set;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

static Set<Integer> result = new HashSet<>();

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 输入处理

int kinds = in.nextInt();

int[] weights = new int[kinds];

int[] cnt = new int[kinds];

for (int i = 0; i < kinds; i++) {

weights[i] = in.nextInt();

}

for (int i = 0; i < kinds; i++) {

cnt[i] = in.nextInt();

}

result.add(0);

// 每次添加一种砝码

for (int i = 0; i < weights.length; i++) {

// 每次添加一个

for (int j = 0; j < cnt[i]; j++) {

ArrayList<Integer> adds = new ArrayList<>(result);

// 出现新重量就追加

for (Integer add : adds) {

result.add(add + weights[i]);

}

System.out.println(result.size());

}

发表于 2024-03-31 01:22:15 回复(0)

Java

kyrieJazz

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            // 读取砝码的种类
            int[] weight = new int[n];
            for(int i = 0; i < n; i++){
                weight[i] = in.nextInt();
            }   
            // 读取砝码的数量
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < n; i++){
                for(int count = in.nextInt(); count > 0; count--){
                    // 整合到同一个序列当中
                    list.add(weight[i]);
                }
            }
            // System.out.println(list);
            
            // 创建一个集合Set
            Set<Integer> set = new HashSet<>();
            // 初始化向集合中添加0
            set.add(0);
            // 遍历序列list
            for(int i : list){
                // 遍历集合Set，对每个Set当中的值加值后，添加到Set当中
                int len = set.size();
                List<Integer> setList = new ArrayList<>();
                // 将set中的值临时存入setList当中用于求和
                for(int j : set){
                    setList.add(j);
                }
                for(int k : setList){
                    set.add(i + k);
                }
            }
            // 统计Set当中的数量，并输出
            System.out.println(set.size());
        }
    }
}

编辑于 2024-03-27 11:28:32 回复(0)

Java

今生能进大厂吗

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            int num = Integer.valueOf(in.nextLine());
            String weight = in.nextLine();
            String weightNum = in.nextLine();
            String[] arr1 = weight.split(" ");
            String[] arr2 = weightNum.split(" ");
            int[] weights = new int[num];//存储所有重量
            int[] weightNums = new int[num];//存储所有数量
            for (int i = 0; i < num; i++) {
                weights[i] = Integer.parseInt(arr1[i]);
                weightNums[i] = Integer.parseInt(arr2[i]);
            }

            Set<Integer> set = new HashSet<>();//存储不重复的砝码重量集合
            set.add(0);//初始化重量0
            for (int i = 0; i < num; i++) {
                int wet = weights[i];//遍历每一个重量
                int wtn = weightNums[i];//遍历重量对应的数量

                Set<Integer> temp = new HashSet<>();//暂存集合
                //遍历数量,注意循环的初始值,排查半天
                for (int j = 1; j <= wtn; j++) {
                    for(Integer w : set){
                        temp.add(w + wet * j);
                    }
                }
                 set.addAll(temp);
            }

            System.out.println(set.size());
        }
    }
}

编辑于 2024-01-09 16:40:46 回复(0)

Java

Kili_66

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String [] weights = in.nextLine().split(" ");
        String [] counts = in.nextLine().split(" ");
        Set<Integer> temp = new HashSet();
        Set<Integer> sets = new HashSet();
        sets.add(0);
        for(int i = 0; i < n; i++){
            temp.clear();
            for(int j = 1; j <= Integer.parseInt(counts[i]); j++){
                for(Integer item : sets){
                    int m = item + Integer.parseInt(weights[i])*j;
                    temp.add(m);
                }
            }
            sets.addAll(temp);
        }
        System.out.println(sets.size());
    }
}

发表于 2023-11-24 14:58:13 回复(0)

Java

逆海崇帆

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Test001 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            int cnt = in.nextInt();
            in.nextLine();
            String weight = in.nextLine();
            String count = in.nextLine();
            String[] weights = weight.split(" ");
            String[] counts = count.split(" ");
            Set<Integer> list = new HashSet<>();
            Set<Integer> set = new HashSet<>();
            set.add(0);
            for (int i = 0; i < cnt; i++) {
                 list.clear();
                 list.addAll(set);
                for (int j = 1; j < Integer.parseInt(counts[i]) + 1; j++) {
                    for (Integer a : list) {
                        int total = a + j * Integer.parseInt(weights[i]);
                        set.add(total);
                    }
                }
            }
            System.out.println(set.size());
        }
    }
}

发表于 2023-10-12 18:42:16 回复(0)