题解 | #装箱问题#
装箱问题
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))
查看25道真题和解析
