求助!!!

求助大佬们:

题目描述

有N包书,数量为a[i],现在需要X本书。我们需要尽可能少的拆开包装。问至少需要拆开多少个包装正好共有X本书。

输入

第一行,两个数N和X。

第二行,N个数A[i]

输出

如果存在挑选的方案,输出一个整数,代表最小的包数;否则输出一行“impossible”(不含引号)。


样例输入

4 6
1 2 3 4

样例输出

2

提示

N<=100

X<=100000

#笔试题目#
全部评论
dp式子推一推
点赞 回复
分享
发布于 2020-02-23 12:18
背包问题,f(i) = min( f(i) , f(i-coin)+1 ) python 实现如下: k = 6 coins = [1, 2, 3, 4] dp = [0] + [float('inf')]*k for i in range(1, k+1):     for coin in coins:         if i  >= coin:             dp[i] = min(dp[i], dp[i-coin]+1) print(dp[-1])
点赞 回复
分享
发布于 2020-02-23 14:59
乐元素
校招火热招聘中
官网直投
动态规划: 用f[i][k]表示前i个包集齐k本书最少需要打开多少包。 f[i][k] = min(f[i-1]][k], f[i-1][k-a[i]]+1) 解释: 对于f[i][k]来说, 若第i个包不打开,则f[i][k]=f[i-1][k],表示前i-1个包集齐k本需要多少个包。 若第i个包打开,则f[i][k]=f[i-1][k-a[i]]+1,表示前i-1个包集齐k-a[i]本数需要多少个包,再加上第i个包。 至于具体第i个包打不打开,取决于哪种选择更小。
点赞 回复
分享
发布于 2020-02-23 15:30

相关推荐

1 1 评论
分享
牛客网
牛客企业服务