您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

装箱问题-简化版本动态规划

题目描述

题目

有一个箱子容量为 V(正整数,0≤V≤20000),同时有n个物品(0 \leq n \leq 30$),每个物品有一个体积(正整数)。

要求 n 个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。

输入描述

输入第一行,一个整数,表示箱子容量。

第二行,一个整数 n,表示有 nn 个物品。

接下来 n 行,分别表示这 n 个物品的各自体积。

输出描述

输出一行,表示箱子剩余空间。

输入输出样例

示例 1

输入

24
6
8
3
12
7
9
7

输出

0

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M

思路

这道题是背包问题的简化版,即不需要管每个物品的价值。我们只需要从这些货物中选出和最接近箱子容量的组合即可。

我们设dp[j]为箱子容积为时,所有货物中选出所得的物品的最接近v的体积。

设计动态转移方程:我们遍历每一个货物i,让箱子体积j从v减小到i的体积,我们有两种选法,一是不拿这个货物,不做任何操作,dp[i][j]等于之间的值dp[i-1][j];另外一种拿这个货物是找到dp[i-1][j-h[i]]即当前的最优解减去h[i]的最优解,dp[i-1][j-h[i]]+h[i]就是我们当前的最优解

状态转移方程如下:

dp[j]=max(dp[j],dp[j-h[i]]+h[i])

代码

v = int(input())
n = int(input())
h = []
dp=[0]*10000
for i in range(n):
    h.append(int(input()))
for i in range(n):
    for j in range(v,h[i]-1,-1):
        dp[j]=max(dp[j],dp[j-h[i]]+h[i])
print(v-dp[v])


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进