免费网站域名查询,百度风云榜电视剧排行榜,韩路做的网站是什么名字,丽江建设网站动态规划就是#xff0c;将任务每一步均记录下来#xff0c;以便将来重复使用时能够直接调用 问题描述#xff1a;给定n个物品#xff0c;每个物品的重量是Wi,价值是Vi#xff0c;但是背包最多能装下capacity重量的物品#xff0c;问我们如何选择才能利益最大化。 这里涉…动态规划就是将任务每一步均记录下来以便将来重复使用时能够直接调用 问题描述给定n个物品每个物品的重量是Wi,价值是Vi但是背包最多能装下capacity重量的物品问我们如何选择才能利益最大化。 这里涉及到建模过程本文章主要讲解代码实现建模过程较为简略。 使用dp[i][j]来表示在容量为j的情况下前i件物品的最大化利益。
情况一放入第i件物品前发现jweight[i]因此dp[i][j]此时仍然是dp[i-1][j]也就是dp[i][j]没有发生变化。 情况二放入第i件物品时发现j weight[i]此时你放入这件物品与否要看放进去以后利益是如何变化的。 ①不放入那么dp[i][j]的值还是dp[i-1][j]。 ②放入那么dp[i][j]的值是dp[i-1][j-weight[i]]value[i]。想一想对不对
那么具体实现代码如下
weight [1,2,5,6,7,9]
value [1,6,18,22,28,36]num 6
capicity 13def fun(num, capicity, weight, value):#构造一个num1行capicity1列的二维数组#便于下标从1开始使用dp np.array([[0]*(capicity1)]*(num1))#dp[i][j]表示第前i件物品在容量为j下的最大价值#最终需要知道dp[num][capicity]也就是dp[6][13]在容量为13情况下前6件物品的最大价值是多少。#进一步的需要知道dp[][]for i in range(1,num1):for j in range(1, capicity1):if j weight[i-1]:dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i-1]]price[i-1])else:dp[i][j] dp[i-1][j]print(dp)fun(num, capicity, weight, value) 核心就在于这个动态转移方程。 d p [ i ] [ j ] m a x { d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w e i g h t [ i ] ] v a l u e [ i ] } dp[i][j] max\{dp[i-1][j],dp[i-1][j-weight[i]]value[i]\} dp[i][j]max{dp[i−1][j],dp[i−1][j−weight[i]]value[i]}
虽写下这篇笔记但有关动态规划的问题还需多多研究加深理解。
