题解 | #装箱问题#

装箱问题

https://www.nowcoder.com/practice/c990bd0bf8e04bfbb19c0964401c8f77?tpId=230&tqId=2383987&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D230

import sys

V = int(input())
n = int(input())

things = [int(input()) for i in range(n)]
#初始化一个dp数组,表示容积为dp[j]的最大的体积
dp =[0 for i in range(V+1)]


#每遍历一次物品,就会更新dp数组一波,
for i in range(len(things)):
#01背包问题倒序遍历背包
    for j in range(V,-1,-1):
        if things[i]<=j:
            dp[j]= max(dp[j],dp[j-things[i]]+things[i])

print(V-max(dp))

全部评论

相关推荐

08-19 19:57
石河子大学 C++
企鹅百度字节的孝子:为啥本科只有两年啊
校招求职吐槽
点赞 评论 收藏
分享
站队站对牛:兄弟 你这是四年就当大一过了吧 也许你校园卡 赚了有五位数了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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