总结经典动态规划——01背包

总结经典动态规划——01背包

题目描述

已知有n 个物品和一个承重为 content 的背包，物品 i 的重量以及价值分别为 weight[i]、 value[i] 。问：应如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

众所周知，这题是动态规划的入门题。那么什么是动态规划？ 我的理解是，当大问题难以解决时，先用求解小问题，然后后面求解大问题的时候我们就可以直接拿着小问题的结果来计算大问题。 对于01背包，大问题就是已知背包容量和物品的重量和价值，让你选择不止一个物品使得背包价值最大。

1. 背包容量小于当前物品重量

2. 背包容量不小于当前物品重量

既然背包容量大于物品重量，我们就一定要装当前的物品吗？答案是不一定能装当前物品，试想就算能装下，若这个物品却不那么之前，那我装了不是亏了吗，还占用背包空间。那什么时候一定能装入呢？综合之前装入背包的物品的情况分析，若装了此物品比不装此物品，背包中价值更大时才能装，引出第二个递推公式:

const vector value = {0, 6, 3, 5, 4, 6}; // n = 5 种物品const vector weight = {0, 2, 2, 6, 5, 4}; //为方便写代码，vector长度为6，0号元素为0const int content = 10; //背包承重

填表顺序：从上到下，一次填一行，表示背包容量从小变大，物品由少变多

模拟填写表格的代码：

/** * @author Leo * 递推公式： * save[i][j] = save[i-1][j] // j < weight[i] * save[i][j] = max(save[i-1][j-weight[i]] + value[i], save[i-1][j]) // j >= weight[i] */vector> count(){ int n = weight.size() - 1; vector> save; save.resize(n + 1); //行 for (int i=0; i= weight[i]){ save[i][j] = max(save[i-1][j-weight[i]] + value[i], save[i-1][j]); }else{ save[i][j] = save[i-1][j]; } } } return save;}

通过表格我们可以确定获得的最大价值，但是我们还不清楚具体选择哪几个物品。

接下来根据表格构造最优解：

vector getSelection(vector> save){ vector select(save.size(), 0); int n = save.size() - 1;//n个物品 int cur_c = save[0].size() - 1;//背包容量 for(int i = n; i > 1; i--){ if(save[i][cur_c] == save[i-1][cur_c]){ select[i] = 0; }else{ select[i] = 1; cur_c -= weight[i]; } } select[1] = save[1][content] > 0 ? 1 : 0; return select;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。