[编程题]称砝码
- 热度指数：216757 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
第一行输入一个整数
代表砝码的个数。
个整数
代表每种砝码的重量。
代表每种砝码的数量。
输出描述:
示例1
输入
2 1 2 2 1
输出
5
说明
个重量为
的砝码，
不放砝码，称重重量为
；
；
。
种，分别是
。
把所有砝码放到一个数组里，转换为组合回溯问题，在每个树枝判断、收集结果。
先把砝码排序，例如[1,1,3,5,6]，加入used数组去重，避免得到[1,3,5]、[1, 3, 5]等重复集合，
且并能减小遍历次数，提高效率，Set集合避免重复输出，超时了。19/20
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 n = in.nextInt();
int[] weights = new int[n];
int[] numbers = new int[n];
for (int i = 0; i < n; i++){
weights[i] = in.nextInt();
}
for (int i = 0; i < n; i++){
numbers[i] = in.nextInt();
}
ArrayList<Integer> map = new ArrayList<>();
for (int i = 0; i < n; i++){
for (int j = 0; j < numbers[i]; j++){
map.add(weights[i]);
}
}
int res = 0;
HashSet<Integer> usedSet = new HashSet<>();
usedSet.add(0);
Collections.sort(map);
int[] used = new int[map.size()];
backtracking(map, usedSet, 0, 0, used);
System.out.println(usedSet.size());
}
}
private static void backtracking(ArrayList<Integer> map,
HashSet<Integer> usedSet, int startindex, int sum, int[] used){
if(!usedSet.contains(sum)){
usedSet.add(sum);
}
for (int i = startindex; i < map.size(); i++){
if (i > 0 && map.get(i) == map.get(i - 1) && used[i - 1] == 0){
continue;
}
used[i] = 1;
sum += map.get(i);
backtracking(map, usedSet, i + 1, sum, used);
sum -= map.get(i);
used[i] = 0;
}
}
}
发表于 2025-07-20 17:37:27
回复(1)
根据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)
想了好半天，突然就开窍了，关键在于每次选择砝码时，和之前的每轮选砝码的所有结果进行一一组合，需要两个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)
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)
原来是我想得太复杂了，我们可以把这个问题拆解到每一次称出的重量，然后再汇总起来
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
回复(1)
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)
问题信息
难度：
80条回答
4387收藏
44823浏览
通过挑战的用户
查看代码-
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号
