称砝码问题

一时失言乱红尘 2022-08-08 05:15 206阅读 0赞

# 题目描述 #

有一组砝码，重量互不相等，分别为 m1 、 m2 、 m3……mn ；它们可取的最大数量分别为 x1 、 x2 、 x3……xn 。   
 现要用这些砝码去称物体的重量 , 问能称出多少种不同的重量。   
Input  
 测试数据第一行一个整数 n （ n<=10 ），表示有多种不同的砝码；   
 第二行 n 个整数（中间用空格分隔）， m1 、 m2 、 m3……mn ，分别表示 n 个砝码的重量；（ 1<=mi<=20 ）   
 第三行 n 个整数（中间用空格分隔）， x1 、 x2 、 x3……xn ，分别表示 n 个砝码可取的最大数量。（ 1<=xi<=20 ）   
Output  
 每组数据输出仅一行，一个整数，表示利用给定的砝码可以称出的不同的重量数。   
 注：包括 0 。   
Sample Input  
2  
1 2  
2 1  
  
Sample Output  
5

//称砝码
    int main() {
    	int n;
    	cin >> n;
    	int max_wight = 0;
    	vector<int> nums(n), wights(n);
    
    	for (int i = 0; i < n; i++)
    		cin >> wights[i];
    	for (int i = 0; i < n; i++) {
    		cin >> nums[i];
    		max_wight += wights[i] * nums[i]; //求最大可称重的值
    	}
    
    	//set内是可以称重的值，元素互斥单调增
    	set<int> s;
    	s.insert(max_wight);
    
    	//进行n次循环；
    	//对于第i次循环，将set中元素从小到大依次取出，
    	//减去k * wights[i]，表示少使用k个质量为wights[i]的砝码
    	//也可以作为可称重的值；只要这个值是大于0的即可。
    	for (int i = 0; i < n; i++) {
    		set<int>::iterator iter = s.begin();
    		while (iter != s.end()) {
    			for (int k = 1; k <= nums[i] && *iter - k * wights[i] > 0; k++)
    				s.insert(*iter - k * wights[i]);
    			iter++;
    		}
    	}
    	s.insert(0);
    	cout << s.size() << endl;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，206人围观）

还没有评论，来说两句吧...

相关阅读

相关【蓝桥杯】砝码称重

[3417. 砝码称重 - AcWing题库][3417. _ - AcWing] 题意： ![29f26757e1174102b819a74e4f568b98.png][

以你之姓@/ 2024年03月30日 10:14/ 0 赞/ 51 阅读

相关 HJ41 称砝码

> [牛客华为机试题库【题号 HJ开头】（重点看）][HJ] > [牛客在线编程算法篇【题号NC开头】][NC] > [剑指offer【题号 JZ开头】][offer_

Love The Way You Lie/ 2024年03月27日 13:56/ 0 赞/ 83 阅读

相关 AcWing——砝码称重

[4942. 砝码称重 - AcWing题库][4942. _ - AcWing] 1、题目给定一个天平和 101 个砝码。 101 个砝码的重量依次为 n⁰,n¹

比眉伴天荒/ 2023年09月27日 18:16/ 0 赞/ 122 阅读

相关砝码称重

题目：有一个天平，有六种砝码，分别重1,2,3,5,10,20克，每种砝码各有5,3,2,2,1,1个，计算天平能称出的重量及种类方法一： include <

Love The Way You Lie/ 2023年07月17日 15:35/ 0 赞/ 15 阅读

相关 P1441-砝码称重

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

淩亂°似流年/ 2023年06月01日 08:52/ 0 赞/ 22 阅读

相关称砝码（C++牛客网）

解题思路：（1）动态规划，dp\[n\]=去重（dp\[n-1\]+\{dp\}+v\[n\]） include<iostream> include<ve

痛定思痛。/ 2022年11月11日 05:12/ 0 赞/ 209 阅读

相关华为OJ称砝码

问题描述：现有一组砝码，重量互不相等，分别为m1、m2……mn；他们可取的最大数量分别为x1、x2……xn。现在要用这些砝码去称物体的重量，问能称出多少中不同的重量

分手后的思念是犯贱/ 2022年10月01日 00:48/ 0 赞/ 216 阅读

相关称砝码问题

题目描述有一组砝码，重量互不相等，分别为 m1 、 m2 、 m3……mn ；它们可取的最大数量分别为 x1 、 x2 、 x3……xn 。现要用这些砝码去称

一时失言乱红尘/ 2022年08月08日 05:15/ 0 赞/ 207 阅读

相关 [编程题]称砝码

> Talk is cheap, show me the code. 一、问题描述现有一组砝码，重量互不相等，分别为m1,m2,m3…mn；每种砝码对应的

太过爱你忘了你带给我的痛/ 2022年07月13日 03:21/ 0 赞/ 208 阅读

相关盾神与砝码称重

package 搜索; import java.io.IOException; import java.io.InputStream; import java.ut

清疚/ 2022年07月12日 12:13/ 0 赞/ 181 阅读