动态规划——01背包问题_背包问题的状态变量是什么

作者：繁依Fanyi0 | 2024-04-11 05:30:32

踩

背包问题的状态变量是什么

前言

前面的文章介绍了动态规划的基本概念以及一些解题技巧，并分析了其中的一些基础问题，包括《爬楼梯》，《不同路径》，《整数拆分》等，这次，我们开始动态规划中的一个新的篇章， 01背包问题。 01背包问题是背包问题中较为简单的一种，背包问题还包括完全背包问题以及多重背包问题，不过从我面试的经历来看，掌握01背包问题和完全背包问题即可

01背包问题

背包问题分类

01背包概念

有N种物品和⼀个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每种物品只有一个（那么这个物品要么被选，要么不被选），求最大可放入背包的物品价值总和

分析

这里有两个变量，分别是物品种类和背包容积，故考虑用二维动态规划来解决问

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/403138