背包问题变种
最少数量货物装箱问题
http://www.nowcoder.com/questionTerminal/37aa8a88a72e47f798a14d63bee61d8f
看了这么多解答，各种回溯法的确可以做，但没有写到点子上，就是一个背包问题的变种
和lintcode 上的换硬币问题是一模一样的：
https://www.lintcode.com/problem/coin-change/description
if __name__ == "__main__":
x = int(input())
# dp[n] 容量为 n 能够装满所需的最小个数
a = [3, 5, 7]
dp = [i for i in range(x+1)]
for i in range(1, x+1):
dp[i] = x+1
for j in a:
if j<=i:
dp[i] = min(dp[i], dp[i-j] + 1)
print(-1 if dp[x]==x+1 else dp[x])
查看15道真题和解析
