首页 > 试题广场 >

称砝码

[编程题]称砝码

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

现有n种砝码，重量互不相等，分别为 m1,m2,m3…mn ；
每种砝码对应的数量为 x1,x2,x3...xn 。现在要用这些砝码去称物体的重量(放在同一侧)，问能称出多少种不同的重量。

注：

称重重量包括 0

数据范围：每组输入数据满足 $1 \le n \le 10 \$ ， $1 \le m_i \le 2000 \$ ， $1 \le x_i \le 10 \$

输入描述:

对于每组测试数据：

第一行：n --- 砝码的种数(范围[1,10])

第二行：m1 m2 m3 ... mn --- 每种砝码的重量(范围[1,2000])

第三行：x1 x2 x3 .... xn --- 每种砝码对应的数量(范围[1,10])

输出描述:

利用给定的砝码可以称出的不同的重量数

示例1

输入

2
1 2
2 1

输出

说明

可以表示出0，1，2，3，4五种重量。

算法知识视频讲解

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)

Java

愤怒的小刺猬说等下个版本吧

三分钟写一个dfs,1秒钟超时，好家伙，厉害了我的哥

发表于 2023-10-10 15:08:55 回复(1)

Java

锰锰在睡觉

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

int a = in.nextInt();

ArrayList<Integer> list = new ArrayList();

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

list.add(in.nextInt());

}

ArrayList<Integer> numbers = new ArrayList();

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

numbers.add(in.nextInt());

}

HashSet<Integer> set = new HashSet();

set.add(0);

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

add(list.get(i), numbers.get(i), set);

}

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

}

private static void add(int a, int b, HashSet<Integer> set) {

HashSet<Integer> set1 =(HashSet<Integer>)set.clone();

for (int s : set1) {

for (int i = 1; i <=b; i++) {

set.add(s + a * i);

}

//System.out.println(set.toString());

}

发表于 2023-09-25 14:52:41 回复(0)

Java

牛客632641331号

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine()); //砝码种数
        String[] s1 = in.nextLine().split(" ");
        String[] s2 = in.nextLine().split(" ");

        int[] weight = new int[n]; //每种砝码重量
        int[] nums = new int[n]; //每种砝码数量

        for (int i = 0 ; i < n ; i++) {
            weight[i] = Integer.parseInt(s1[i]);
            nums[i] = Integer.parseInt(s2[i]);
        }

        Set<Integer> set = new HashSet<>(); //存储可以称重的结果，自动去重了
        set.add(0); //初始化,0为题目设定

        for(int i = 0; i< n ; i++){
            int w = weight[i]; //重量
            int num = nums[i]; //数量

            for(int j = 0; j< num;j++){
                Set<Integer> tmp = new HashSet<>();
                set.forEach(x->{ //原set结果更新到临时set中
                    tmp.add(x+w);
                });
                set.addAll(tmp); //插入新加入的结果
            }

        }

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

    }
}

发表于 2023-09-10 14:15:48 回复(0)

Java

绝地飞鸿1993

import java.util.*;
import java.util.stream.Collectors;
// 注意类名必须为 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 types = in.nextInt();
            int[] heights = new int[types];
            for (int i = 0; i < types; i++) {
                heights[i] = in.nextInt();
            }

            int[] nums = new int[types];
            for (int i = 0; i < types; i++) {
                nums[i] = in.nextInt();
            }

            List<Integer> fama = new ArrayList<>();


            for (int i = 0; i < nums.length; i++) {
                int tmp = nums[i];
                for (int j = 0; j < tmp; j++) {
                    fama.add(heights[i]);
                }
            }
            //Integer[] array = fama.toArray(fama.toArray(new Integer[0]));
            Collections.sort(fama);
            LinkedList<Integer> path = new LinkedList<>();
            LinkedList<List<Integer>>  res = new LinkedList<>();
            backtrack(fama, 0, path, res);

            HashSet<Integer> set = new HashSet<>();
            set.addAll(res.stream().map(list -> list.stream().reduce(0, (a,
                                        b)->a + b)).collect(Collectors.toList()));

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

    private static void backtrack(List<Integer> fama, int start,
                                  LinkedList<Integer> path, LinkedList<List<Integer>> res) {

        res.add(new ArrayList<>(path));

        for (int j = start; j < fama.size(); j++) {
            if (j > start && fama.get(j) == fama.get(j - 1)) {
                continue;
            }

            path.addLast(fama.get(j));
            backtrack(fama, j + 1, path, res);
            path.removeLast();
        }

    }
}

超时了，请教下

发表于 2023-08-29 09:42:50 回复(0)

Java

牛客117087621号

set集合遍历的时候不能修改的，debug了半天不知道为啥总循环不完。基础知识还是薄弱，最后还是chatgpt推荐我定义多一个set集合进

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        HashSet<Integer> set = new HashSet<>();
        HashSet<Integer> tempSet = new HashSet<>();
        set.add(0);
        tempSet.add(0);
        //n种砝码
        int n = in.nextInt();
        //砝码重量
        int weight[] = new int[n];
        for (int i = 0; i < n; i++) {
            int a = in.nextInt();
            weight[i] = a;
        }
        //各重量对应的砝码数量
        for (int k = 0; k < n; k++) {
            int a = in.nextInt();
            //对于权重为weight[k]的砝码有a个，set集合为已经确定好的重量，***，直接有一个加一个进去遍历让它自己查重，就这么笨比^^
            for (int j = 1; j <= a; j++) {
                Iterator<Integer> it = set.iterator();
                while(it.hasNext()){
                    int temp = it.next();
                    tempSet.add(temp + weight[k]);
                }
                set.addAll(tempSet);
            }
        }
        System.out.print(set.size());
    }
}

行复制，我是废物***

编辑于 2023-07-06 21:32:09 回复(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 的区别
        int n=in.nextInt();
        ArrayList<Integer> weight=new ArrayList<>();
        ArrayList<Integer> num=new ArrayList<>();
        ArrayList<Integer> fama=new ArrayList<>();
        //砝码重量添加到集合
        for(int i=0;i<n;i++){
            weight.add(in.nextInt());
        }
        //砝码个数添加到集合
        for(int i=0;i<n;i++){
            num.add(in.nextInt());
        }
        //将每个砝码的所有情况添加到fama集合中，如1，1，2
        for(int i=0;i<n;i++){
            for(int j=0;j<num.get(i);j++){
                fama.add(weight.get(i));
            }
        }
        //升序排列
        Collections.sort(fama);
        //保存能称重的情况
        ArrayList<Integer> list=new ArrayList<>();
        list.add(0);
        for(int i=0;i<fama.size();i++){
            int nowsize=list.size();
            for(int j=0;j<nowsize;j++){
                //对于保存在list集合中的重量，每个重量+砝码重量如果没有保存到集合中，说明是新的重量，那么保存到集合中
                if(!list.contains(list.get(j)+fama.get(i))){
                    list.add(list.get(j)+fama.get(i));
                }
            }
        }
        //集合个数就是砝码称重数
        System.out.print(list.size());
    }
}

发表于 2023-05-28 15:49:08 回复(0)

Java

きゅうきゅうにょりつれい

import java.util.Scanner;
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int N;
    static int[] m;
    static int[] n;
    static int[] arr;
    static int sum = 0;
    static Set<Integer> flagList = new TreeSet<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        m = new int[N];
        n = new int[N];
        int len = 0;
        for (int i = 0; i < N; i++) {
            m[i] = in.nextInt();
        }
        for (int i = 0; i < N; i++) {
            n[i] = in.nextInt();
            len += n[i];
        }
        arr = new int[len];
        int idx = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < n[i]; j++) {
                arr[idx++] = m[i];
            }
        }
        dfs(0);
//        for (Integer sum : flagList) {
//            System.out.println(sum);
//        }
        System.out.println(flagList.size());
    }


    static void dfs(int i) {
        flagList.add(sum);
        if (i >= arr.length) {
            return;
        }
        sum += arr[i];
        dfs(i + 1);
        sum -= arr[i];
        dfs(i + 1);
    }
}

代码超时能过16个样例,不知道能不能优化, 看网上都是用的循环,往set中添加元素, 这种方法肯定是我想不出来的,想看看有没有递归接出来这道题的方案

发表于 2023-05-26 16:57:40 回复(1)

Java

Yjaun

import java.util.*;

public class DeepSearch {
    public static class Weigh{
        int val;
        int count = 0;
        Weigh(int x){ this.val = x; }
    }
    public static class Answer{
        int val;
        Answer(int x){ this.val = x; }
    }
    public static int countWeigh(List<Weigh> weighs){
        int count = 0;
        for(int i = 0; i < weighs.size(); i++){
            count += weighs.get(i).count;
        }
        return count;
    }
    private static void recurse(int index, List<Weigh> weights, Answer answer){
        if(countWeigh(weights) == 0){
            answer.val++;
        }
        else{
            if(weights.get(index).count >= 1){
                recurse(index, weights, answer);
                weights.get(index).count--;
            }
            else{
                recurse(index+1, weights, answer);
            }
        }
    }
    private static int calWeighKinds(List<Weigh> weights, Answer answer){
        recurse(0, weights, answer);
        return answer.val;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Weigh> weighs= new LinkedList<>();
        int n = scanner.nextInt();
        for(int i = 0; i < n; i++){
            weighs.add(new Weigh(scanner.nextInt()));
        }
        for(int i = 0; i < n; i++){
            weighs.get(i).count = scanner.nextInt();
        }
        Answer answer = new Answer(0);
        System.out.println(calWeighKinds(weighs, answer));
    }
}

深度搜索的思路做，栈溢出了，各位帮忙看看哪里有问题

发表于 2023-05-15 14:25:15 回复(0)

Java

清逸人

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

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

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int total = in.nextInt();
        int[] weights = new int[total];
        int[] num = new int[total];
        for (int i = 0; i < total; i++) {
            weights[i] = in.nextInt();
        }
        for (int i = 0; i < total; i++) {
            num[i] = in.nextInt();
        }
        System.out.println(selectWeight(weights, num, total - 1).size());
    }
    // 前 i的集合
    private static Set<Integer> selectWeight(int[] weights,
            int[] num,
            int i) {
        Set<Integer> s = new HashSet();
        if (i == 0) {
            for (int index = 0; index <= num[i]; index++) {
                s.add(weights[i] * index);
            }
            return s;
        }
        Set<Integer> prefixSet = selectWeight(weights, num, i - 1);
        for (int index = 0; index <= num[i]; index++) {
            for (Integer item : prefixSet) {
                s.add(weights[i] * index + item);
            };
        }
        return s;
    }
}

发表于 2023-05-10 17:17:28 回复(0)

Java

牛客604637229号

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNext()) { // 注意 while 处理多个 case

int n = in.nextInt();

List<Integer> listM = new ArrayList<Integer>();//重量集合

List<Integer> listX = new ArrayList<Integer>();//数量集合

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

int mn = in.nextInt();

listM.add(mn);

}

listM.add(0);//给设置0重量

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

int xn = in.nextInt();

listX.add(xn);

}

listX.add(1);//给0重量设置1个

//给每个重量设置能够称重的集合

Map<Integer,List<Integer>> map = new HashMap<Integer,List<Integer>>();

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

List<Integer> list = new ArrayList<Integer>();

for(int j=1;j<=listX.get(i);j++){//每个砝码重量的个数，从1开始

list.add(listM.get(i)*j);

// list.add(0-listM.get(i)*j);//注意，如果是两边都可以加砝码，则要加上这一句代码

}

map.put(listM.get(i),list);//设置每个重量设置能够称重的集合

}

TreeSet<Integer> set = new TreeSet<Integer>();//当前所能称重的所有重量集合

set.add(0);//默认设置0

for(Map.Entry<Integer,List<Integer>> entry:map.entrySet()){

List<Integer> list = entry.getValue();//每个重量砝码的可称重量集合

List<Integer> retlist = new ArrayList<Integer>();//每个重量砝码跟原来的砝码可称重集合

for(Integer ins:list){

Iterator it = set.iterator();

while(it.hasNext()){

Integer nxt = (Integer)it.next();

retlist.add(ins+nxt);//当前所能称重的所有重量集合，与下一个重量的砝码所称重量集合循环迭代相加

}

set.addAll(retlist);//TreeSet具有过滤和排序的作用

}

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

}

发表于 2023-04-16 01:39:03 回复(0)

Java

林深时er

import java.util.*;
import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String line;
        // 注意 hasNext 和 hasNextLine 的区别
        while ((line = reader.readLine()) != null) { // 注意 while 处理多个 case
            int n = Integer.parseInt(line);//砝码的种类数
            int[] weights = new int[n];//每一种砝码的重量
            int[] numbers = new int[n];//每一种砝码对应的数量
            String[] s1 = reader.readLine().split(" ");
            String[] s2 = reader.readLine().split(" ");
            for (int i = 0; i < n; i++) {
                weights[i] = Integer.parseInt(s1[i]);
                numbers[i] = Integer.parseInt(s2[i]);
            }
            ArrayList<Integer> list = new ArrayList<>();//保存所有的砝码
            Set<Integer> set = new HashSet<>();
            int k=0;
            for(int i=0;i<n;i++){
                for(int j=0;j<numbers[i];j++){
                    // arr[k++] = weights[i];
                    list.add(weights[i]);
                }
            }
            //现在得到了数组1 1 2，接下来我们遍历数组就可以得到最终想要的答案了
            for(int i=0;i<list.size();i++){ //遍历砝码
                ArrayList<Integer> list1 = new ArrayList<>(set);
                if(!set.contains(list.get(i))) set.add(list.get(i));
                for(int j=0;j<list1.size();j++){ //遍历list1集合
                    int tmp = list.get(i)+list1.get(j);
                    if(!set.contains(tmp)){
                        set.add(tmp);
                    }
                }
            }
            System.out.println(set.size()+1); //加1是因为要把0的重量加上。
        }
    }
}

发表于 2023-03-31 20:37:43 回复(0)