你有一个背包,最多能容纳的体积是V。 现在有n种物品,每种物品有任意多个,第i种物品的体积为  ,价值为 。 (1)求这个背包至多能装多大价值的物品? (2)若背包恰好装满 ,求至多能装多大价值的物品?-笔试面试资料

这是qklbishe.com第18323 篇笔试面试资料
提供答案分析,通过本文《你有一个背包,最多能容纳的体积是V。
现在有n种物品,每种物品有任意多个,第i种物品的体积为  ,价值为 。
(1)求这个背包至多能装多大价值的物品? (2)若背包恰好装满 ,求至多能装多大价值的物品?-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

你有一个背包,最多能容纳的体积是V。
现在有n种物品,每种物品有任意多个,第i种物品的体积为你有一个背包,最多能容纳的体积是V。          现在有n种物品,每种物品有任意多个,第i种物品的体积为                   ,价值为                  。          (1)求这个背包至多能装多大价值的物品?    (2)若背包恰好装满 ,求至多能装多大价值的物品? ,价值为你有一个背包,最多能容纳的体积是V。          现在有n种物品,每种物品有任意多个,第i种物品的体积为                   ,价值为                  。          (1)求这个背包至多能装多大价值的物品?    (2)若背包恰好装满 ,求至多能装多大价值的物品?
(1)求这个背包至多能装多大价值的物品?
(2)若背包恰好装满,求至多能装多大价值的物品?
Python 3

你有一个背包,最多能容纳的体积是V。          现在有n种物品,每种物品有任意多个,第i种物品的体积为                   ,价值为                  。          (1)求这个背包至多能装多大价值的物品?    (2)若背包恰好装满 ,求至多能装多大价值的物品? zh.

import sys  # 空间复杂度使用二维数组 def ks(n, V, P, M):     dp = [[float("-inf") for _ in range(V+1)] for _ in range(n+1)]     for x in range(len(dp)):         dp[x][0] = 0 #     for y in range(len(dp[0])): #         dp[0][y] = 0     for i in range(1, n+1):         for j in range(1, V+1):             if j >= P[i]:                 for k in range(0, j//P[i]+1):                     dp[i][j] = max(dp[i][j], dp[i-1][j-k*P[i]]+k*M[i])             else:                 dp[i][j] = dp[i-1][j]     print(max(max(dp)))     if dp[-1][-1] == float("-inf"):         print(0)     else:         print(dp[-1][-1])          # 通过19/20,算法超时         def ks_B(n, V, P, M):     dp = [float("-inf") for _ in range(V+1)]     dp[0] = 0     for i in range(1, n+1):         for j in range(V, -1, -1):             for k in range(0, j//P[i]+1):                 dp[j] = max(dp[j], dp[j-k*P[i]]+k*M[i])     print(max(dp))     if dp[-1] != float("-inf"):         print(dp[-1])     else:         print(0)     return   # 满足要求 # 思考:容量序列遍历为何可以使用正向序列?而且序列的起点可以为P[i]? # 完全背包问题,物品i没有数量限制; # 当 j < P[i]时,容量不足以容纳物品 i, #   相当于d[i][j] = d[i-1][j], 在O(n)复杂度的算法中也就是不更新内容,所以可以设置起点为P[i]  def ks_C(n, V, P, M):     dp = [float("-inf") for _ in range(V+1)]     dp[0] = 0     for i in range(1, n+1):         for j in range(P[i], V+1):             dp[j] = max(dp[j], dp[j-P[i]]+M[i])     print(max(dp))     if dp[-1] != float("-inf"):         print(dp[-1])     else:         print(0)     return   line1 = [int(x) for x in sys.stdin.readline().split()] n = line1[0] V = line1[1]   P = [0] M = [0] for line in sys.stdin:     tmp = [int(x) for x in line.split()]     P.append(tmp[0])     M.append(tmp[1]) ks_C(n, V, P, M)      

今天 15:00:36 回复(0)
Python 3

你有一个背包,最多能容纳的体积是V。          现在有n种物品,每种物品有任意多个,第i种物品的体积为                   ,价值为                  。          (1)求这个背包至多能装多大价值的物品?    (2)若背包恰好装满 ,求至多能装多大价值的物品? 区块链毕设学生760622808号

补一个python3,与前一个背包问题的区别在于调整了dp循环顺序,从容量1到容量n进行循环,这样后续的dp就可以用到之前用过的物品
def ans():     n, size = map(int,input().split(" "))     v, w = [] , []     for _ in range(n):         t1, t2 = map(int,input().split(" "))         v.append(t1)         w.append(t2)          dp1 = [0] * (size+1)     dp2 = [float("-inf")] * (size+1)     dp2[0] = 0          for i in range(n):         for j in range(1,size+1):             if j >= v[i]:                 dp1[j] = max(dp1[j], dp1[j-v[i]] + w[i])                 dp2[j] = max(dp2[j], dp2[j-v[i]] + w[i])          print(dp1[-1])     print(dp2[-1] if dp2[-1] != float("-inf") else 0) ans()

今天 13:30:35 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 你有一个背包,最多能容纳的体积是V。 现在有n种物品,每种物品有任意多个,第i种物品的体积为  ,价值为 。 (1)求这个背包至多能装多大价值的物品? (2)若背包恰好装满 ,求至多能装多大价值的物品?-笔试面试资料

提供最优质的资源集合

立即查看 了解详情