动态规划1—-背包问题
大家好，这次给大家分享的题会比以往难一点，学会了这道题的解题思想，对动态规划的掌握就更上一层楼了- 下面先给大家讲有关于动态规划的两个概念（其实在上两次的题中我们一直有在用）
- 最优子结构
对于一个问题，我们可以拆分成很多相似的子问题，并且要算出原问题的最优解之前，
必须先算出子问题的最优解。例如跳台阶的那道题，f(n-1),f(n-2)…这些就是子问题
，我们要算出f(n)之前，就必须先算出f(n-1),f(n-2)。 - 状态
所谓的状态就是指这个问题解决了没有（包括子问题）。我们用1表示已解决，用0表示
未解决（这个用什么数字表示都行）。例如当我们求出了f(n-1)时，就把它的状态记录
为1，否则记录为0。记录状态主要是为了防止大量的重复求解
问题：
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装
入背包中物品的总价值最大?
个人感觉这道经典的0-1背包问题还是挺难的，
反正当时看了好几遍才看懂，才理解它的做法
解析：
当然，对于这道题，如果你想要暴力递归的方法做也是可以的。例如我们可以把所有
物品看出一个集合，然后把所有子集都求出来，然后看看那个集合的物品装的下且价值
最高。不过时间复杂度是2的n次方。指数增长的复杂度自己掂量。
-
暴力递归的做法如下(C++)（我就不带大家找递归结束等条件了）
int n, C;//n表示物品的数量，C表示背包能承载的重量 int v[Max_n+1], w[Max_n+1];//v[i]表示地i个物品的价值，w[i]表重量 //从第i个物品挑选总重量小于j的部分 //**下标从1开始** int solve(int i, int j){ int sum; if(i > n){//已经没有物品了（因为下标从0开始的） sum = 0; }else if(j < w[i]){ //这个物品装不下 sum = solve(i+1, j);//挑选下一个物品 }else{ //物品装的下 //分是否挑选物品两种情况 //不装，则尝试挑选 下一个 //装的话，背包容量变为j-w[i],单价值多了v[i] sum = max(solve(i+1, j), solve(i+1, j-w[i])+v[i]); return sum; } } int main(){ solve(n, C); } - 重复算了同一个函数很多遍，如同
- 数据变量说明：
- 对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态可以取0和1.我们设物品i的装入状态为xi,xi∈ (0,1)。
- 数据：物品个数n=5,物品重量w[n]={0，2，2，6，5，4},物品价值V[n]={0，6，3，5，4，6},C=10，（为了方便说明，小标从1开始）
- 对于m(i,j)就表示可选物品为i…n背包容量为j(总重量)时背包中所放物品的最大价值。
- 建立如下方格图（其实就是一个二维数组）
{
//采用从底到顶的顺序来设置m[i][j]的值
//首先放w[n]
for(int j = 0; j <= c; j++){
if(j < w[n]) m[n][j] = 0; //j小于w[n],放不下，把所对应的值设为0，否则就为可以放置
else m[n][j] = v[n];
}
//对剩下的n-1个物品进行放置。
int i;
for(i = n-1; i >= 1; i--){
for(int j = 0; j <= c; j++)
if(j < w[i]) {
m[i][j] = m[i+1][j];//如果j < w[i]则，表示放不下，它等于上一个位置的值。
}else {
//否则，就考虑是否要放置，原理和递归做法相似
m[i][j] = max(m[i+1][j], m[i+1][j-w[i]] + v[i]);
}
return a[1][c];//m[1][c]就是所求最大值
}
- 动态规划的实质就是，将问题化为求解子问题，前一个子问题最值问题求解了，如果你找到子问题与当前问题的关系，那么当前问题就解决了，是一个迭代的过程。
另外，将搜索进行记忆化，也就是说把算过的记录起来。 - 下面给大家推荐一道类似的题，做法和这个背包的几乎一样，考考大家，给大家练练手。
问题描述：
小明是一个喜欢看动画片的人，自从成为ACMer（ACM爱好者）之后，他又迷上了网上做题。做题让他快乐，不过这也是需要付出精力的！！
假设有n道题，Lian做出第i道题后，他可以获得的快乐指数将增加gethappy[i]，而消耗掉的精力将是losspow[i]。
假设小明初始的快乐指数为1，精力为2000。可以理解，如果他消耗完了所有的精力那他得到再多的快乐都没有用。
你的任务就是帮他计算他所能得到的最多的快乐指数，且最后他依然有多余的精力（即至少为1）。
输入格式
第一行输入一个整数n，表示有n个人。(n<=50)
第二行输入n个整数，表示gethappy[1]到gethappy[n]
第三行输入n个整数，表示losspow[1]到losspow[n]。
输出格式
一个整数，表示小明所能获得的最大快乐指数。
输入样例
3
15 23 61
350 1301 1513
输出样例
77
—————
- 希望大家能有所收获
- 下次会给大家推荐一些数据结构与算法的书（都是自己看过的，感觉还不错）。
- 如果大家想要这道题的答案，可以在公众号回复小明的快乐获取。
下面二维码
