最小邮票数

[编程题]最小邮票数

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

有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可。

输入描述:

    有多组数据，对于每组数据，首先是要求凑成的邮票总值M，M<100。然后是一个数N，N〈20，表示有N张邮票。接下来是N个正整数，分别表示这N张邮票的面值，且以升序排列。

输出描述:

      对于每组数据，能够凑成总值M的最少邮票张数。若无解，输出0。

示例1

输入

10
5
1 3 3 3 4

输出

算法知识视频讲解

Python

TimeMac

def getComNum(nowIndex,nowSum,nowStampNum):
    if nowIndex >= n:
        return
    if stamps[nowIndex] + nowSum > m:
        return
    elif stamps[nowIndex] + nowSum == m:
        global result
        result = min(result,nowStampNum+1)
        getComNum(nowIndex+1,nowSum,nowStampNum)
    else:
        getComNum(nowIndex+1,nowSum+stamps[nowIndex],nowStampNum+1)
        getComNum(nowIndex + 1, nowSum,nowStampNum)
while True:
    try:
        m = int(input())
        n = int(input())
        stamps = list(map(int,input().split()))
        result = float('inf')
        getComNum(0,0,0)
        if result == float('inf'):
            result = 0
        print(result)
    except Exception:
        break

编辑于 2018-10-10 23:15:40 回复(0)

Python

哈哈哈哈哈哈哈哈201710271141466

while True:
try:
a=input()
y=input()
b=[]
b=map(int,raw_input().split())
b=sorted(b,reverse=True)
c=sorted(b,reverse=False)
d=[]
for t in range(len(b)):
s=a-c[t]
n=1
nnt=b[:]
nt=c[t]
nnt.remove(nt)
for x in nnt:
if s-x>0:
s-=x
n+=1
elif s-x==0:
n+=1
d.append(n)
break
if len(d)!=0:
print(min(d))
else:
print(0)
except:
break

发表于 2017-11-02 17:09:50 回复(0)