【C++ 算法入门】动态规划-01背包问题
·
大家好，我是一名正在学习c++和算法的大学生，这是我在CSDN的第一篇博客，是关于01背包的算法题。我以后打算在此记录自己的刷题过程，备战蓝桥杯。下面是我对与01背包问题的解法心得
一 原题复现
有 n 件物品和一个容量为 V 的背包。
第 i 件物品的体积是 w[i]，价值是 v[i]。
每件物品只能选一次（选 或 不选）。
求在不超过背包容量的前提下，能装下的最大总价值。
二 思路分析
对于刚接触算法的大学生来说，面对这道题大多无从下手，我想最好是暴力解法，对于n件物品无非两种选择（选/不选）考虑其时间复杂度---2的n次方。选或不选采用暴力解法容易想到递归，但时间复杂度较高。亟待优化。
动态规划，在这题上的体现我认为是建立一个dp［i］［j］i表示前i个物品，j表示背包容量，dp数组就是表示在背包容量为j的情况下，对前i个物品进行选择所得到的最大价值。下面是代码以及我的注释：
以上包括了我的代码的思考过程。本人能力有限，对于01背包的思考或有漏洞，或解释浅显。欢迎大家指正。
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
21
0- 0
已为社区贡献1条内容
所有评论(0)