动态规划进阶篇1---背包问题

动态规划进阶篇1—-背包问题

大家好，这次给大家分享的题会比以往难一点，
学会了这道题的解题思想，对动态规划的掌握
就更上一层楼了

• 下面先给大家讲有关于动态规划的两个概念（其实在上两次的题中我们一直有在用）

1. 最优子结构 对于一个问题，我们可以拆分成很多相似的子问题，并且要算出原问题的最优解之前，必须先算出子问题的最优解。例如跳台阶的那道题，f(n-1),f(n-2)…这些就是子问题，我们要算出f(n)之前，就必须先算出f(n-1),f(n-2)。
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){//已经没有物品了（因为下标从1开始的） 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(){ int sum = solve(n, C); }
• 重复算了同一个函数很多遍，如下图
• 所用数据n=4,C=5,(w,v)={(2,3),(1,2),(3,4),(2,2)};

大家可以尝试用下把solve(i,j)这个函数是否算过的状态保存起来，然后计算之前先查看是否已经算过。如果算过则直接返回。递归式的动态规划就不带大家做了,主要是多接触下其他做法勒，题就要多做才能熟能生巧

下面介绍用递推式的动态规划

• 数据变量说明：

1. 对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态可以取0和1.我们设物品i的装入状态为xi,xi∈ (0,1)。
2. 数据：物品个数n=5,物品重量w[n]={0，2，2，6，5，4},物品价值V[n]={0，6，3，5，4，6},C=10，（为了方便说明，小标从1开始）
3. 对于m(i,j)就表示可选物品为i…n背包容量为j(总重量)时背包中所放物品的最大价值。
4. 建立如下方格图（其实就是一个二维数组）
5. 过程如下

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

代码如下（C++）

nt solve(int m[][11],int w[],int v[],int n)//n代表物品的个数   
{  
//采用从底到顶的顺序来设置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 m[1][c];//m[1][c]就是所求最大值
}

• 动态规划的实质就是，将问题化为求解子问题，前一个子问题最值问题求解了，如果你找到子问题与当前问题的关系，那么当前问题就解决了，是一个迭代的过程。 另外，将搜索进行记忆化，也就是说把算过的记录起来。
• 下面给大家推荐一道类似的题，做法和这个背包的几乎一样，考考大家，给大家练练手。

问题描述：

小明是一个喜欢看动画片的人，自从成为ACMer（ACM爱好者）之后，他又迷上了网上做题。做题让他快乐，不过这也是需要付出精力的！！ 假设有n道题，Lian做出第i道题后，他可以获得的快乐指数将增加gethappy[i]，而消耗掉的精力将是losspow[i]。 假设Lian初始的快乐指数为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