[编程题]称砝码
- 热度指数：218726 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
第一行输入一个整数
代表砝码的个数。
个整数
代表每种砝码的重量。
代表每种砝码的数量。
输出描述:
示例1
输入
2 1 2 2 1
输出
5
说明
个重量为
的砝码，
不放砝码，称重重量为
；
；
。
种，分别是
。
import java.util.Scanner;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
static Deque<Integer> path = new LinkedList<>();
static Set<Integer> set = new HashSet<>();
static ArrayList<ArrayList<Integer>> result = new ArrayList<>();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int kind = in.nextInt();
int[] kinds = new int[kind];
int[] num=new int[kind];
for(int i=0;i<kind;i++){
kinds[i]=in.nextInt();
}
int sum=0;
for(int i=0;i<kind;i++){
num[i]=in.nextInt();
sum+=num[i];
}
int[] arr = new int[sum];
int count=0;
for(int j=0;j<kind;j++){
int numOfCur=num[j];
while(numOfCur!=0){
arr[count]=kinds[j];
count++;
numOfCur--;
}
}
Arrays.sort(arr);
backTracking(arr,0);
// System.out.println(Arrays.toString(arr));
int rrr=0;
for(ArrayList<Integer> list: result){
int curSum=0;
for(Integer snum: list){
curSum+=snum;
// System.out.print(snum);
}
if(!set.contains(curSum)){
rrr++;
set.add(curSum);
}
// System.out.println();
}
System.out.println(rrr);
}
public static void backTracking(int[] arr,int index){
result.add(new ArrayList<>(path));
for(int i=index;i<arr.length;i++){
if ( i > index && arr[i - 1] == arr[i] ) {
continue;
}
path.addLast(arr[i]);
backTracking(arr,i+1);
path.removeLast();
}
}
} 想法是将所有砝码放到一个数组里面，然后将数组进行组合，组合相加后去重从而获得总次数，但是会超时！！！！写了很久不想浪费，做一个纪念。
发表于 2022-03-30 10:54:16
回复(1)
坑点：0也要加进set里面
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in = new Scanner(System.in);
while(in.hasNextInt()){
int n = in.nextInt();
int m[] = new int [n];
int x[] = new int [n];
for(int i = 0; i < n; i++)
m[i] = in.nextInt();
for(int i = 0; i < n; i++)
x[i] = in.nextInt();
category(n, m, x);
}
in.close();
}
public static void category(int n, int m[], int x[]){
HashSet<Integer> set = new HashSet<Integer>();
set.add(0);
for(int i = 0; i < n; i++){
List<Integer> list = new ArrayList<Integer>(set);
for(int j = 0; j <= x[i]; j++){
for(int k = 0; k < list.size(); k++){
set.add(list.get(k) + j * m[i]);
}
}
}
System.out.println(set.size());
}
}
发表于 2021-03-17 14:38:35
回复(0)
java hashset转数组对每个元素加砝码重量
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String n1 = null;
while ((n1 = bf.readLine()) != null) {
int n = Integer.parseInt(n1);
String[] s1 = bf.readLine().split(" ");
String[] s2 = bf.readLine().split(" ");
int[] weight = new int[s1.length];
int[] nums = new int[s2.length];
for (int i = 0; i < n; i++) {
weight[i] = Integer.parseInt(s1[i]);
nums[i] = Integer.parseInt(s2[i]);
}
System.out.println(fama(n, weight, nums));
}
}
public static int fama(int n, int[] weight, int[] nums) {
HashSet<Integer> set = new HashSet<>();
set.add(0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < nums[i]; j++) {
Object[] d = set.toArray();
for (int k = 0; k < d.length; k++) {
set.add((Integer) d[k] + weight[i]); //set中的已有元素再加上当前砝码重量
}
}
}
return set.size();
}
}
发表于 2020-09-26 11:36:20
回复(0)
#include "string.h"
#include <stdio.h>
#include "stdlib.h"
//期初放第一个砝码，就在该重量标志位置1，继续放砝码之前判断重量标志位哪些为1
//然后放上砝码，把相应标志位置1.
int main (void)
{
int num;
while (scanf("%d",&num)!=EOF)
{
int table[2][10]={0};
int i,j,k,q=0;
for (i=0;i<2;i++)
for (j=0;j<num;j++)
scanf("%d",&table[i][j]); //构建二维数组，第一行是不同砝码规格的重量，第二行是数量
int weight=0;
for (i=0;i<num;i++) weight=weight+table[0][i]*table[1][i]; //计算出最大重量
int p[10000]={0};
p[0]=1; //期初标志位
for (i=0;i<num;i++) //选取规格
{
for (j=0;j<table[1][i];j++) //该规格下的数量
{
for (k=weight;k>=0;k--) //遍历重量表，寻找重量标志位
{
if (p[k]==1) p[k+table[0][i]]=1; //刷新重量标志位
}
}
}
for (i=0;i<10000;i++)
{
if (p[i]==1) q++;
}
printf("%d\r\n",q);
}
}
发表于 2020-09-06 14:58:07
回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
//需要读懂题 --
//按照砝码重量和数量，逐个推到vector中，且比较去重
using namespace std;
int main()
{
int n;
while(cin >> n)
{
int m[10]={0};
int x[10]={0};
for(int i = 0;i<n;i++)
cin>>m[i];
for(int i = 0;i<n;i++)
cin>>x[i];
vector<int> weight;
weight.push_back(0);//现将0放进数组，因为称重重量包括0
//开始进行逐个砝码进行比较和确认最终情况
for(int i = 0;i<n;i++)
{
int len = weight.size();
for(int j = 1;j<=x[i];j++)
{
int tmp = j*m[i];
if(i == 0) weight.push_back(tmp);
for(int z = 0;z<len;z++)
{
int res = weight[z] + tmp;
if(find(weight.begin(),weight.end(),res) == weight.end())//如果当前计算的重量数组里面没有，那么就放进去
weight.push_back(res);
}
}
}
cout<<weight.size()<<endl;
}
return 0;
}
发表于 2020-07-16 11:38:26
回复(1)
真羡慕你们用高级语言，，，参考第一个的思路693ms
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct result_s
{
int sum;
struct result_s *next;
}SUM_S;
int main()
{
int total_num = 0;
int per_qlt[10] = {0};
int per_num[10] = {0};
SUM_S *psum_head = NULL;
SUM_S *psum_old_head = NULL;
SUM_S *psum_new = NULL;
SUM_S *psum_temp = NULL;
SUM_S *psum_temp2 = NULL;
int is_exist = 0;
int sum_size = 0;
int index_type = 0;
int use_per_type = 0;
int temp_sum = 0;
//scanf("%d", &total_num);
while(scanf("%d", &total_num) != EOF)
{
for(index_type = 0; index_type < total_num; index_type++)
{
scanf("%d", &per_qlt[index_type]);
}
for(index_type = 0; index_type < total_num; index_type++)
{
scanf("%d", &per_num[index_type]);
}
psum_head = (SUM_S *)malloc(sizeof(SUM_S));
memset(psum_head, 0, sizeof(SUM_S));
for(index_type = 0; index_type < total_num; index_type++)
{
psum_old_head = psum_head;
for(use_per_type = 1; use_per_type <= per_num[index_type]; use_per_type++)
{
psum_temp = psum_old_head;
while(psum_temp != NULL)
{
temp_sum = psum_temp->sum + (use_per_type * per_qlt[index_type]);
printf("(sum %d + use%dqlt%d) ", psum_temp->sum, use_per_type, per_qlt[index_type]);
psum_temp2 = psum_head;
while(psum_temp2 != NULL)
{
if(temp_sum == psum_temp2->sum)
{
is_exist = 1;
}
psum_temp2 = psum_temp2->next;
}
if(is_exist == 0)
{
psum_new = (SUM_S *)malloc(sizeof(SUM_S));
memset(psum_new, 0, sizeof(SUM_S));
psum_new->sum = temp_sum;
psum_new->next = psum_head;
psum_head = psum_new;
sum_size++;
printf("add %d\n", psum_new->sum);
}
is_exist = 0;
psum_temp = psum_temp->next;
}
}
}
printf("%d\n", sum_size + 1);
while(psum_head->next != NULL)
{
psum_temp = psum_head;
psum_head = psum_head->next;
free(psum_temp);
}
psum_head->sum = 0;
sum_size = 0;
}
return 0;
}
发表于 2019-08-11 23:26:05
回复(0)
int fama(int n, int *weight, int *nums)
{
vector<int> now;
set<int> noww;
set<int> tempset;
int temp = 0;
for (int i = 0; i <= nums[0]; i++)
{
noww.insert(i*weight[0]);
}
for (int i = 1; i < n; i++)
{
for (auto j : noww)
{
for (int k = 0; k <= nums[i]; k++)
{
tempset.insert(k*weight[i] + j);
}
}
noww = tempset;
tempset.clear();
}
for (auto i : noww)
{
temp++;
//cout << i << endl;
}
{
vector<int> now;
set<int> noww;
set<int> tempset;
int temp = 0;
for (int i = 0; i <= nums[0]; i++)
{
noww.insert(i*weight[0]);
}
for (int i = 1; i < n; i++)
{
for (auto j : noww)
{
for (int k = 0; k <= nums[i]; k++)
{
tempset.insert(k*weight[i] + j);
}
}
noww = tempset;
tempset.clear();
}
for (auto i : noww)
{
temp++;
//cout << i << endl;
}
发表于 2018-08-06 14:30:06
回复(0)
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <list>
#include <deque>
#include <algorithm>
#include <cctype>
#include <iomanip>
#include<cstdlib>
#include <functional>
#include <bitset>
using namespace std;
//称砝码
void fama()
{
int num;
while (cin >> num)
{
int num1 = num;
vector<int> weight;
vector<int> mount;
while (num1)
{
--num1;
int w;
cin >> w;
weight.push_back(w);
}
int sum = 0;
for (int i = 0; i < num;++i)
{
int m;
cin >> m;
sum += weight[i] * m;
mount.push_back(m);
}
vector<int> dp(sum + 1, 0);
dp[0] = 1;
for (int i = 0; i < num; ++i)
{
for (int j = 0; j < mount[i]; ++j)
{
for (int k = sum; k >= weight[i]; --k)
{
if (dp[k - weight[i]] == 1)
dp[k] = 1;
}
}
}
int result = 0;
for (auto elem : dp)
{
if (elem == 1)
++result;
}
cout << result << endl;
}
}
int main()
{
fama();
return 0;
}
发表于 2016-08-18 18:36:59
回复(1)
import java.util.Scanner;
import java.util.TreeSet;
public class Main{
public static void main(String[] args){
Scanner s=new Scanner(System.in);
while(s.hasNext()){
int n=s.nextInt();
int[] arr1=new int[n];
int[] arr2=new int[n];
int total=0;
for(int i=0;i<n;i++)
arr1[i]=s.nextInt();
for(int i=0;i<n;i++){
arr2[i]=s.nextInt();
total=total+arr1[i]*arr2[i];
}
TreeSet<Integer> set=new
TreeSet<Integer>();
set.add(total);
for(int i=0;i<n;i++){
Object[] set1=set.toArray();
for(Object a:set1){
int j=1;
while(j<=arr2[i]){
set.add((Integer)a-j*arr1[i]);
j++;
}
}
}
System.out.println(set.size());
}
}
}
发表于 2016-08-04 23:13:12
回复(1)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc= new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();//输入数量
Integer[] ws = new Integer[n];
for(int i=0;i<n;i++){
ws[i] = sc.nextInt();
}
List<Integer> list = new ArrayList<Integer>();//所有砝码数
for(int i=0; i < n; i++){
int num = sc.nextInt();
for(int j = 0;j < num; j++){
list.add(ws[i]);
}
}
HashSet<Integer> set = new HashSet<>();//存放所有可能的结果
set.add(0);//初始一个0
for(int i = 0 ; i < list.size(); i++){//其实是进行排列组合,但是这里我们用结果进行存储计算
List<Integer> tmp = new ArrayList<Integer>(set);
for(int j = 0; j< tmp.size();j++){
set.add(tmp.get(j)+list.get(i));
}
}
System.out.println(set.size());
}
}
}
发表于 2022-02-25 17:14:40
回复(0)
该题就是回溯算法的子集问题。JAVA版本如下，但是会超时，这个还要怎么优化啊😅
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
/**
* @author m
* @Description 称砝码
* 思路：
* 1.求全排列的子集
* 2.对子集中所有元素，各自相加
* 3. 相同点元素和去重
* @creat 2021-07-20
*/
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String nn;
while((nn = bf.readLine())!= null){
int n = Integer.parseInt(nn);
String mm = bf.readLine();
String[] m = mm.trim().split(" ");
String xx = bf.readLine();
String[] x = xx.trim().split(" ");//每个砝码的数量
//子集来做：
int N=0;
for(int i=0; i<x.length;i++){
N += Integer.parseInt(x[i]);
}
String[] choice = new String[N];
int k=0;//choice的索引
//遍历x数组，将对应的砝码添加到choice中
for(int i=0;i<x.length;i++){
int num = Integer.parseInt(x[i]);
for(int j=0;j<num;j++){
choice[k++] = m[i];
}
}
//输出：
Set res= new HashSet();
int sum=0;
recur(choice,0,sum,res);
System.out.println(res.size());
}
}
static void recur(String[] choice, int start,int sum, Set res){
res.add(sum);
for(int i=start;i<choice.length;i++){
//做选择：
sum += Integer.parseInt(choice[i]);
//递归回溯：
recur(choice,i+1,sum,res);
//撤销选择
sum -= Integer.parseInt(choice[i]);
}
}
}
发表于 2021-07-21 14:00:32
回复(0)
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
int main()
{ int n; while(cin>>n) { int a[n],b[n]; set<int> s={0},t={0}; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) cin>>b[i]; for(int i=0;i<n;i++) { for(int k=1;k<=b[i];k++) for(auto it:t) s.insert(it + k*a[i]); t = s; } cout<<s.size()<<endl; } return 0;
}
发表于 2018-06-03 01:28:13
回复(0)
//以第一个砝码为基础，在其基础上不断添加，如示例：
//砝码1的数量位2，则三种情况：0，1，2
//砝码2的数量位1，则两种情况：0，2
//在砝码3种的基础上，添加砝码2的两种情况，分别为：0，1，2；2，3，4；去掉重复情况，则为0，1，2，3，4
//依次类推，得出n种砝码的情况 import java.util.*;
public class Main{
public static int fama(int n, int[] weight, int[] nums){
Set<Integer> set = new HashSet<Integer>();
for(int i = 0; i <= nums[0]; i++){
set.add(weight[0] * i);
}
for(int i = 1; i < n; i++){
List<Integer> list = new ArrayList<Integer>(set);
for(int j = 0; j <= nums[i]; j++){
for(int k = 0; k < list.size(); k++){
set.add(list.get(k) + j * weight[i]);
}
}
}
return set.size();
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int n = in.nextInt();
int[] weight = new int[n];
int[] nums = new int[n];
for(int i = 0; i < n; i++){
weight[i] = in.nextInt();
}
for(int i = 0; i < n; i++){
nums[i] = in.nextInt();
}
System.out.println(fama(n, weight, nums));
}
in.close();
}
}
发表于 2017-03-18 16:34:22
回复(9)
while True: try: a = int(input()) weight = list(map(int,input().split())) count = list(map(int,input().split())) fm,temp,ans = [],[],[0] # 将所有砝码放入列表 for i in range(a): for j in range(count[i]): fm.append(weight[i]) # 称重 for i in fm: temp = set(ans) for j in temp: ans.append(j+i) # 去重 print(len(set(ans))) except: break
编辑于 2020-03-04 17:41:41
回复(12)
/*思路：输入砝码种类n; 输入砝码质量w[i]; 输入砝码个数c[i]； 输出 可以拼凑的质量个数 w1 w2 w3 w4 ...... wn c1 c2 c3 c4 ...... cn 对于前i个砝码： （不同质量为Q[i])则 Q[i]=Q[i-1]+k*w[i]; -->0<=k<=c[i]; Q[i]在Q[i-1]的基础上，对Q[i-1]个不同的重量，分别添加k个砝码i; 在添加的过程中去除重复情况 c[i]表示N个不同砝码相应的数量 c[1~~n]; 则（结果）:Q[i]=(Q[i-1]+k*w[i])--(减去)添加过程中重复的个数 */
JAVA版参考：
import java.util.*; public class Main{ public static void main(String[] args){ Scanner cin=new Scanner(System.in); while(cin.hasNext()){ int n=cin.nextInt();//砝码种类 int[] weights=new int[n]; int[] numbers=new int[n]; for(int i=0;i<n;i++) weights[i]=cin.nextInt(); for(int i=0;i<n;i++) numbers[i]=cin.nextInt(); int result=function(n,weights,numbers); System.out.println(result); } cin.close(); } public static int function(int n,int[] weights,int[] numbers){ Set<Integer> set=new HashSet<Integer>(); for(int i=0;i<=numbers[0];i++) set.add(i*weights[0]); for(int i=1;i<n;i++){//从第二个砝码开始 List<Integer>list =new ArrayList<Integer>(set); for(int j=1;j<=numbers[i];j++){//遍历砝码的个数 for(int k=0;k<list.size();k++) set.add(list.get(k)+j*weights[i]); } } return set.size(); } }
C++版本参考
#include<iostream> #include<vector> #include<set> #include<algorithm> using namespace std; int main() { int n;//砝码数 int m[10]={0};//每个砝码的质量 int x[10]={0};//每个砝码的数量 while(cin>>n){ for(int i=0;i<n;i++) cin>>m[i]; for(int i=0;i<n;i++) cin>>x[i]; vector<int>weights; //存所有已经称出的砝码的质量。 /*先将第一个砝码称出的质量入队。*/ weights.push_back(0);//初始化weights数组 for(int i=1;i<=x[0];i++) weights.push_back(i*m[0]);//将第一个砝码能称出的质量入队 for(int i=1;i<n;i++){//前多少个砝码 //weights.push_back(m[i]); int len=weights.size();//记录已经称出砝码质量便于下面for循环 for(int j=1;j<=x[i];j++){//遍历该质量的砝码数 for(int k=0;k<len;k++){ int w=weights[k]+j*m[i];//将该质量的砝码数依次与前面所有的砝码数相加 //去重操作 if(find(weights.begin(),weights.end(),w)==weights.end())//如果之前没有这个质量的砝码就将其入队 weights.push_back(weights[k]+j*m[i]); } } } cout<<weights.size()<<endl; } }
编辑于 2016-07-22 15:19:55
回复(10)
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
int main()
{
/*从砝码1开始分析，假设前i个砝码能称出的不同重量为Q[i],那么Q[i]一定是这样计算出来的：在Q[i-1]的基础上，对Q[i-1]个不同的重量，分别添加k个砝码i，再添加的过程中除去重复情况。
//假设：w[N]表示N个不同重量的砝码（例子中N=6），w[0~N-1]。
// c[N]表示N个不同砝码相应的数量，c[1~N]。
//则：Q[i] = (Q[i-1] + k*w[i])-添加过程中重复的个数。其中0=<k<=c[i]。网上博客搜的解题思路*/
int n ;//砝码数
int m[10] = { 0 };//每个砝码的质量
int x[10] = { 0};//每个砝码的数量
while (cin >> n)
{
for (int i = 0; i < n; i++)
{
cin >> m[i];
}
for (int i = 0; i < n; i++)
{
cin >> x[i];
}
vector<int>weigths;//存所有已经称出的砝码的质量。
/*先将第一个砝码称出的质量入队。*/
weigths.push_back(0);//初始化weigths数组
for (int i = 1; i <= x[0]; i++)
{
weigths.push_back(i*m[0]);//将第一个砝码能称出的所有质量入队。
}
for (int i = 1; i < n; i++)//前多少个砝码
{
//weigths.push_back(m[i]);
int len = weigths.size();//记录已经称出的砝码质量便于下面for循环使用
for (int j = 1; j <= x[i]; j++)//遍历该质量的砝码数
{
for (int z = 0; z < len; z++)
{
int wei = weigths[z] + j*m[i];//将该质量的砝码数依次与前面所有的砝码数相加
if (find(weigths.begin(), weigths.end(), wei) == weigths.end())//如果之前没有这个质量的砝码就将其入队
weigths.push_back(weigths[z] + j*m[i]);
}
}
}
//set<int>wi(weigths.cbegin(), weigths.cend());//这一步是为了将weigths中的数字进一步去重保证正确性。
cout << weigths.size() << endl;
//cout << wi.size() << endl;
}
//system("pause");
return 0;
}
编辑于 2016-05-28 17:45:40
回复(22)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n;
while(cin>>n){
vector<int> weight(n);
vector<int> num(n);
for(int i=0;i<n;i++)
cin>>weight[i];
for(int i=0;i<n;i++)
cin>>num[i];
vector<int> ans;
for(int i=0;i<=num[0];i++){
ans.push_back(i*weight[0]);
}
for(int j=1;j<n;j++){
int size=ans.size();
for(int i=1;i<=num[j];i++)
for(int m=0;m<size;m++){
if(find(ans.begin(),ans.end(),ans[m]+i*weight[j])==ans.end())
ans.push_back(ans[m]+i*weight[j]);
}
}
cout<<ans.size()<<endl;
}
return 0;
}
编辑于 2016-08-09 13:05:31
回复(4)
思路是参考题解里大部分才用的set集合，每个砝码与set里的每个重量相加，只不过我用的是list，可以用下标取元素。
import sys a = [] for line in sys.stdin: a.append(line[:-1]) for i in range(0, len(a), 3): s = [0] m, x = a[i + 1].split(), a[i + 2].split() # print(s, m, x) # 遍历砝码重量 for j in range(len(m)): # 遍历对应重量砝码个数 for _ in range(int(x[j])): # 遍历现有重量 for k in range(len(s)): # 依次与现有重量相加 new = s[k] + int(m[j]) # 产生新的重量就加入列表 if new not in s: s.append(new) print(len(s))
发表于 2021-10-07 09:18:26
回复(1)
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
/**
* @author Yuliang.Lee
* @version 1.0
* @date 2021/9/18 11:03
* 称砝码：
现有一组砝码，重量互不相等，分别为m1,m2,m3…mn；
每种砝码对应的数量为x1,x2,x3...xn。现在要用这些砝码去称物体的重量(放在同一侧)，问能称出多少种不同的重量。
注：称重重量包括0
* 解题关键：
【意识到迭代逻辑，n个砝码能够称重的重量数一定是基于n-1个砝码称重数的基础上的】
利用集合去重的性质，用set缓存能得到的称重重量，以示例为例，先在集合里面添加0，
当第一个砝码进来的时候；
{0} 变成 {0,0+1} -> {0,1}
当第二个砝码进来之后；
{0，1} 变成 {0，1，0+1，1+1} --> {0,1,2}
当第三个砝码进来之后；
{0,1,2} 变成{0，1，2，0+2，1+2，2+2} ---> {0,1,2,3,4}
最终set集合中的元素个数即为能称出的重量种数。
* 示例：
输入：
2
1 2
2 1
输出：
5
*/
public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
// 砝码种类数
int n = in.nextInt();
// 砝码重量
int[] weight = new int[n];
for (int i = 0; i < n; i++) {
weight[i] = in.nextInt();
}
// 所有砝码的集合
List<Integer> scales = new ArrayList<>();
for (int i = 0; i < n; i++) {
// 砝码不同重量对应的个数
int quantity = in.nextInt();
for (int j = 0; j < quantity; j++) {
scales.add(weight[i]);
}
}
// 设能够称重的重量去重集合为set
Set<Integer> set = new HashSet<>();
// 初始化，集合需包含称重重量为0
set.add(0);
// 迭代逻辑：n个砝码能够称重的重量数一定是基于n-1个砝码称重数的基础上的
for (Integer scale : scales) {
int size = set.size();
Integer[] tmp = new Integer[size];
tmp = set.toArray(tmp);
for (int i = 0; i < size; i++) {
set.add(tmp[i] + scale);
}
}
// 输出总共能称出的重量数
System.out.println(set.size());
}
}
}
发表于 2021-09-18 12:48:21
回复(0)
//1. 看题中例子，0也算一种重量
//2. 逐步添加砝码，去掉重复重量
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int N;
while (cin >> N)
{
vector<int> m(N, 0), x(N, 0), w = { 0 };
for (auto &i : m)
cin >> i;
for (auto &i : x)
cin >> i;
for (int j = 1; j <= x[0]; j++)//先push进第一种砝码的所有可能重量
w.push_back(j*m[0]);
int temp = w.size();
for (int i = 1; i < N; i++)
{
for (int j = 1; j <= x[i]; j++)
for (int k = 0; k < temp; k++)
if (find(w.begin(), w.end(), j*m[i] + w[k]) == w.end())//避免重量重复
w.push_back(j*m[i] + w[k]);
temp = w.size();
}
cout << temp << endl;
}
return 0;
}
法2：今天试了用set容器，还挺方便，贴上代码
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
int main()
{
int N;
while (cin >> N)
{
vector<int> m(N, 0), x(N, 0);
set<int> w = { 0 }, temp = {0};
for (auto &i : m)
cin >> i;
for (auto &i : x)
cin >> i;
for (int i = 0; i < N; i++)
{
for (int k = 1; k <= x[i]; k++)
for (auto it : temp)
w.insert(k*m[i] + it);
temp = w;
}
cout << w.size() << endl;
}
return 0;
}
编辑于 2017-06-20 10:18:32
回复(9)
问题信息
难度：
375条回答
4431收藏
45743浏览
通过挑战的用户
查看代码-
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号
