现有n种砝码，重量互不相等，分别为 m1,m2,m3…mn ；
每种砝码对应的数量为 x1,x2,x3...xn 。现在要用这些砝码去称物体的重量(放在同一侧)，问能称出多少种不同的重量。
注：
称重重量包括 0
数据范围：每组输入数据满足 
， 
， 
[编程题]称砝码
- 热度指数：200320 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
对于每组测试数据： 第一行：n --- 砝码的种数(范围[1,10]) 第二行：m1 m2 m3 ... mn --- 每种砝码的重量(范围[1,2000]) 第三行：x1 x2 x3 .... xn --- 每种砝码对应的数量(范围[1,10])
输出描述:
利用给定的砝码可以称出的不同的重量数
示例1
输入
2 1 2 2 1
输出
5
说明
可以表示出0，1，2，3，4五种重量。
原来是我想得太复杂了，我们可以把这个问题拆解到每一次称出的重量，然后再汇总起来
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)
使用前缀和和动态规划的方法来计算可以称出的不同重量。在利用一个布尔数组来记录能达到的重量。
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
回复(0)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
问题信息
难度：
74条回答
3945收藏
41928浏览
通过挑战的用户
查看代码-
2023-03-02 16:26:09
-
2023-01-10 22:56:28 -
2023-01-07 17:01:38 -
2022-10-28 15:21:35
-
2022-10-27 22:39:47
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
