您的位置:首页 >资讯 > 科技数码问答 >

✨动态规划之0-1背包问题(详解+分析+原码)✨

导读 背包问题可是动态规划的经典案例之一🧐,它就像是一个装宝贝的游戏,每个物品都有自己的重量和价值,而你的背包也有最大承重限制🎒。你需要...

背包问题可是动态规划的经典案例之一🧐,它就像是一个装宝贝的游戏,每个物品都有自己的重量和价值,而你的背包也有最大承重限制🎒。你需要选择哪些物品放入背包,使得在不超过背包容量的前提下,总价值最大化💎。

首先,我们要明确状态转移方程:`dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])`,其中`dp[i][j]`表示前i个物品中,在容量为j时的最大价值。这个公式告诉我们,对于每一个物品,我们可以选择拿或者不拿,取两者中的较大值👀。

接着,我们通过一个简单的例子来理解:假设你有3件物品,重量分别为{2, 3, 4},价值分别为{3, 4, 5},背包最大容量为5。通过填表法一步步计算,最终得到最大价值为7💰。

最后,附上代码实现👇:

```python

def knapsack(weights, values, capacity):

n = len(weights)

dp = [[0](capacity+1) for _ in range(n+1)]

for i in range(1, n+1):

for j in range(capacity+1):

if j >= weights[i-1]:

dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])

else:

dp[i][j] = dp[i-1][j]

return dp[n][capacity]

weights = [2, 3, 4]

values = [3, 4, 5]

capacity = 5

print(knapsack(weights, values, capacity)) 输出结果为7

```

用动态规划解决0-1背包问题,就像是一场智慧与策略的较量,快来试试吧!🚀

免责声明:本文由用户上传,如有侵权请联系删除!