装箱问题

[编程题]装箱问题

热度指数：6685 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个箱子容量为V（正整数，0 ≤ V ≤ 20000），同时有n个物品（0＜n ≤ 30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入描述:

1个整数，表示箱子容量
1个整数，表示有n个物品
接下来n行，分别表示这n个物品的各自体积

输出描述:

1个整数，表示箱子剩余空间。

示例1

输入

输出

算法知识视频讲解

Python 3

3hg713-j5r

bigBox = int(input())
n= int(input())
box=[]
for x in range(n):
    box.append(int(input()))
# box.sort()
dp =[0]*(bigBox+2)
dp[0]=1 ##不装
for b in box:  
    j = bigBox
    while j>=b:
        if dp[j]==0:
            dp[j]= dp[j-b]
        j-=1
i=bigBox
while not dp[i]:
    i-=1
print(bigBox-i)

https://www.bilibili.com/video/BV12S4y1i7B9/?

发表于 2022-06-27 00:15:54 回复(0)