首页 > 试题广场 >

称砝码

[编程题]称砝码

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

$\hspace{15pt}$ 对于给定的 $n$ 种砝码，重量互不相等，依次为 $m_1, m_2, \dots, m_n$ ，数量依次为 $x_1, x_2, \dots, x_n$ ，
$\hspace{15pt}$ 现在要用这些砝码去称物体的重量（放在同一侧），问能称出多少种不同的重量。特别地，称重重量包括 $0$ 。

输入描述:

第一行输入一个整数  代表砝码的个数。
第二行输入  个整数  代表每种砝码的重量。
第三行输入  个整数  代表每种砝码的数量。

输出描述:

输出一个整数，代表利用给定的砝码可以称出的不同的重量数。

示例1

输入

2
1 2
2 1

输出

说明

在这个样例中，有  个重量为  的砝码， 个重量为  的砝码。称重方式如下：
不放砝码，称重重量为  ；
放  个重量为  的砝码，称重重量为  ；
放  个重量为  的砝码，称重重量为  ；
放  个重量为  的砝码、 个重量为  的砝码，称重重量为  ；
放  个重量为  的砝码、 个重量为  的砝码，称重重量为  。
因此，能称出的不同重量有  种，分别是  。

算法知识视频讲解

Python

大溪地渔民

while True:
    try:
        n, weights, counts = int(input()), list(map(int, input().split())), list(map(int, input().split()))
        total = []
        for i in range(n):
            for j in range(counts[i]):
                total.append(weights[i])
        unique_weights = {0}
        for w in total:
            temp = []
            for uw in unique_weights:
                temp.append(uw+w)
            unique_weights = unique_weights | set(temp)
        print(len(unique_weights))
    except:
        break

发表于 2020-12-16 16:07:20 回复(0)

Python

JeremyStar

while True:
    try:
        n = int(input().strip())  # 不同重量的砝码的种数n
        weights = list(map(int, input().strip().split(' ')))  # 每种砝码的具体重量的列表
        nums = list(map(int, input().strip().split(' ')))  # 每种砝码的个数的列表
        combines = [0] * n  # 初始化不同重量的列表
        for i in range(n):
            # 单纯地看第i种重量的砝码mi，能形成多少种重量的组合(砝码个数取：0,1，...xi个)
            combines_i = [weights[i] * num for num in range(0, nums[i]+1)]
            # 将'刚得到的第i种砝码的重量可能列表'与'原来的重量可能列表'进行组合，生成新的重量可能列表
            combines = list(set([a+b for a in combines_i for b in combines]))
        # combines即为最终的不同重量的列表
        print(len(combines))
    except:
        break

发表于 2020-12-04 21:28:58 回复(0)

Python

牛客61640270号

这为什么又不对，求大佬指教

import itertools

a = input()
b = input()
c = input()
d = []
listb = list(b.split(" "))
listc = list(c.split(" "))
for i in range(0,len(listc)):
d.append(list(range(0,int(listc[i])+1)))
f = []
for n in itertools.product(*d):
f.append(n)
e = []
for ff in f:
s = 0
for j in range(0,len(listc)):
s += int(ff[j]) * int(listb[j])
e.append(s)
print(len(set(e)))

发表于 2020-10-27 23:27:55 回复(0)

Python

公子i吃鱼

while True:
    try:
        n, weight, count = int(input()), list(map(int, input().split())), list(map(int, input().split()))
        tmp = [w for w, c in zip(weight, count) for i in range(c)]
        res = {0}
        for i in tmp:
            res_copy = res.copy()
            for j in res_copy:
                res.add(j+i)
        print(len(res))
    except:
        break

发表于 2020-09-28 10:00:49 回复(0)

Python

君临天下201804050931706

while True:
    try:
        n = int(input())
        weights = list(map(int,input().split()))
        counts = list(map(int,input().split()))
        fama,sumWeight=[],[0]
        #首先把所有砝码展平
        for i in range(n): #n种砝码
            for j in range(counts[i]): #每种砝码的个数
                fama.append(weights[i]) #按照数量放入砝码
        #称重
        for i in fama:
            temp = set(sumWeight)
            for j in temp:
                sumWeight.append(j+i)
        #显示称重范围
        print(len(set(sumWeight)))
    except:
        break

发表于 2020-07-19 18:36:48 回复(0)

Python

心怀高远，脚踏实地

while 1:
    try:
        N, weight, num = int(input()), input().split(), input().split()
        mylist = []
        for i in range(len(weight)):
            for j in range(int(num[i])):
                mylist.append(int(weight[i]))
        totalw = [0]
        t = 0
        newlist = []
        for k in mylist:
            newset = set(totalw)
            for h in newset:
                totalw.append(h+k)
        print(len(set(totalw)))

    except:
        break

惭愧，初始代码因为循环过多无法输出，看了评论区大佬的观点才想明白。。。

发表于 2020-04-27 16:42:53 回复(0)

Python

朝夕_

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)

Python

牛客32134662号

while True:
    try:
        n = int(input())
        wei = list(map(int, input().split()))
        num = list(map(int, input().split()))
        diffwei = set()
        diffwei.add(0)
        for i in range(n):
            for j in range(num[i]):
                for k in list(diffwei):
                    diffwei.add(k+wei[i])
        print(len(diffwei))
    except:
        break

用set()直接加入就好啦

发表于 2020-02-18 18:03:41 回复(3)

Python

欧巴禾

n = int(input())
m = list(map(int, input().split()))
x = list(map(int, input().split()))
diff = {0} for i in range(n):  temp = diff.copy() for j in range(x[i]):  for k in temp:  d = k + m[i] * (j + 1) if d not in temp:  diff.add(d) print(len(diff))

发表于 2019-05-21 17:37:13 回复(0)

Python

CassielLee

/* 利用set自动去重，感觉题目没有说清楚，n表示砝码的种类，不是砝码的数量，另外就是要
加上重量为0的情况……*/
def getWeight(n,weight,num):
    res = {0}
    for i in range(n):
        temp = res.copy()
        for j in range(1,num[i]+1):
            for k in temp:
                res.add(k + weight[i]*j)
    return len(res)

while True:
    try:
        n = int(input())
        weight = list(map(int,input().split()))
        num = list(map(int,input().split()))
        print(getWeight(n,weight,num))
    except:
        break

发表于 2018-08-28 20:27:35 回复(1)

Python

tVvCreep

存贮临时可称重范围最好用set而不是list，set访问更快，较list更省时

发表于 2017-09-05 20:10:16 回复(0)

Python

牛客565260号

import sys

while True:

try:

n = int(sys.stdin.readline().strip())

weight = map(int,sys.stdin.readline().split())

number = map(int,sys.stdin.readline().split())

count = set()

for i in range(number[0]+1):

count.add(i*weight[0])

j = 1

while j<n:

k = 1

mid = list(count)

while k <=number[j]:

for s in range(len(mid)):

count.add((k*weight[j]+mid[s]))

k +=1

j+=1

print len(count)

except:

break

发表于 2017-08-17 19:36:36 回复(0)

Python

CrazyVertigo

基本思路：先把所有的砝码放到列表v当中，然后逐一放到列表out[]里面，并逐个和列表out[]中的数相加。然后再对代码进行优化，一开始超时，然后超过内存，引入集合后就可以了。
Python中集合的概念有时候非常好用~~~~

try:
    while True:
        N = int(raw_input())
        u = map(int,raw_input().split())
        v = map(int,raw_input().split())
        buf = []
        out = [0]
        for i in range(N):
            for j in range(1,v[i]+1):
                buf.append(u[i])
        for m in buf:
            outbuf = list(set(out[:]))
            for n in outbuf:
                out.append( m+n )
        print len(set(out))
except:
    pass

编辑于 2017-03-12 20:37:17 回复(0)

Python

此番风景

 def solution(w, n):
    cnt = set( w[0]*i for i in range(n[0]+1)) # 初始set
    for i in range(1, len(w)): # 遍历砝码重量
        tmp = cnt.copy() # copy一份
        for j in range(n[i]+1): # 处理砝码对应的数量
            for k in tmp: # 当前可以称的重量
                tmp_w = w[i]*j + k
                if tmp_w not in cnt:
                    cnt.add(w[i]*j + k) # set自动去重
    return len(cnt)

import sys
try:
    while 1:
        line = sys.stdin.readline().strip()
        if not line:
            break
        w = sys.stdin.readline().strip()
        w = map(int, w.split())
        n = sys.stdin.readline().strip()
        n = map(int, n.split())
        print solution(w, n)
except:
    pass

编辑于 2016-09-10 22:11:57 回复(0)