背包问题变种

最少数量货物装箱问题

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])
全部评论

相关推荐

缓解焦虑的最好方法是回家。鼠鼠昨天上午考完了本科阶段的最后一场考试,大概率考得稀烂,但是没多想,考完立马收拾行李,坐上了提前约好的顺风车飞奔回家。虽然家和学校很近,只有一百多公里的路程,但距离上次回家也已经有三四个月了。每次想回家,期间总有考试、毕业设计、面试、实习等等各种各样的原因,没办法回去,待在学校和公司的每一天也都充斥着无形的压力和焦虑。现在终于完成了答辩,考完了试,公司那边也请了假,是时候回去一趟了。没有提前通知爸妈,想给他们一个惊喜。下午提前到了家,他俩还在上班,只好让外公外婆来给我开门。因为我的回家,晚上外婆在厨房格外忙碌,做了满满一大桌子菜,填饱了我天天吃外卖的肚子。晚上也没空...
梦想是成为七海千秋:取决于家庭吧?其实回家更焦虑了,每天起床父母都问实习找好了没简历投递了没今天有没有面试,但是又没有什么结果,玩两下手机父母就会说你看你啥也没找到为什么天天就知道刷手机,怎么不去学习…我现在就希望我能永远在外面实习,报喜不报忧,等拿到一个好offer再回家
点赞 评论 收藏
分享
04-25 18:13
五邑大学 Java
后来123321:大二两段实习太厉害了,我现在大二连面试都没有
点赞 评论 收藏
分享
LemontreeN:有的兄弟有的我今天一天面了五场,4个二面一个hr面
投递字节跳动等公司7个岗位
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务