数据结构和算法分析程序员java工程师

动态规划1—-背包问题

2018-05-19  本文已影响7人  帅地

动态规划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次方。指数增长的复杂度自己掂量。

  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. 建立如下方格图(其实就是一个二维数组)

int 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 a[1][c];//m[1][c]就是所求最大值

}




—————


你们的支持便是我最大的动力,支持就关注我的公众号吧:di201805

下面二维码









上一篇 下一篇

猜你喜欢

热点阅读