一文读懂背包问题

（点击上方公众号，可快速关注）转自：刘毅https://www.61mon.com/index.php/archives/188/好文投稿， 请点击 → 这里了解详情问题展开有 N 件物品和一个容量为 V 的背包。第 i 件物品的体积是 Ci，其价值是 Wi。求解，在不超过背包容量情况下，将哪些物品装入背包可使价值总和最大。基本思路这是最基础的背包问题，特点是：每种物品仅有一件。状态 F[i,v] 表示前 i 件物品中选择若干件放在容量为 v 的背包中，可以取得的最大价值。转移方程：对于第 i 件物品，有放与不放两种选择。若选择不放，F[i,v]=F[i−1,v]；若选择放，v−Ci 确保有足够的空间，随之 F[i,v]=F[i−1,v−Ci]+Wi。代码展开/** * * author 刘毅（Limer） * date   2017-03-17 * mode   C++ */#include #include using namespace std;int m ………………………………