🎒📚背包问题九讲笔记:完全背包📦✨
2025-03-18 01:35:06
•
来源:
导读 今天来聊聊完全背包问题!假设我们有 🎒容量为9的背包,手头有 🏆3种物品可供选择。完全背包的特点是每种物品可以取无限次,是不是很有趣...
今天来聊聊完全背包问题!假设我们有 🎒容量为9的背包,手头有 🏆3种物品可供选择。完全背包的特点是每种物品可以取无限次,是不是很有趣?💪
首先,明确状态转移方程:`dp[j] = max(dp[j], dp[j - weight[i]] + value[i])`。这里`dp[j]`表示容量为`j`时的最大价值,而`weight[i]`和`value[i]`分别是第`i`种物品的重量和价值。💡
举个栗子:假如三种物品的重量分别为 `[2, 3, 4]`,价值分别为 `[3, 4, 5]`。从`j=0`到`j=9`逐一更新`dp[j]`,你会发现最终当`j=9`时,最大价值可达 `12`!🎉
完全背包的关键在于“无限取用”,所以遍历物品时需要多次尝试放入背包。通过动态规划一步步优化,就能轻松解决啦!🎯🔥
如果你也有类似的问题,不妨试试这种思路哦~💬💖
免责声明:本文由用户上传,如有侵权请联系删除!