背包问题-01背包

下面分析01背包问题.这是所有背包问题的基础

有N件物品和一个容量为W的背包,每种物品 均只有一件.第 i 件物品的容量是w[i],价值是v[i].求解将哪些物品装入背包可使价值总和最大.

定义dp[i][j] := 从前i个物品中选出总重量不超出j的物品是总价是的最大值.每个背包标号为1,2,3…n.是从1开始的.

选择每个背包的时候都有两种选择:选择或这不选.所有第i个物品的价值应该是:max(dp[i-1][j],dp[i-1][j-w[i]]+v[j]).

初始值: i = 0时,dp[i][j] = 0;

dp[i-1][j]表示不选择第i个背包,就跟前一个背包的价值是一样的.

dp[i-1][j-w[i]]+v[i]表示选择第i个背包,那么选择第 i-1 个背包时候容量的限制值就是j-w[i]而不是j,dp[i-1][j-w[i]]就是第i-1个背包的价值.

所以该问题的状态方程如下:

dp[0][j] = 0;
if(j < w[i]) // 此时装不下第i个背包
  dp[i][j] = dp[i-1][j];
else
  dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);

下面以一个具体的实例来分析:

n = 4,w = 5;

(w,v) = ((2,3),(1,2),(3,4),(2,2))

根据状态方程画出表格结果如下:

最后是这个采用动态规划解决此问题的代码

 1:  #include <stdio.h>
 2:  #include <stdlib.h>
 3:  
 4:  /** author: cjr
 5:    * date: 2014-08-11
 6:    * 01背包问题-linux下测试通过
 7:    */
 8:  
 9:  // 这么简单的函数就不解释了吧!
10:  int max(int a,int b)
11:  {
12:    if(a > b)
13:        return a;
14:    else
15:        return b; 
16:  }
17:  
18:  int main()
19:  {
20:    int i,j,n,max_weight;
21:    int **dp = NULL,*weight=NULL,*value=NULL;
22:    scanf("%d %d",&n,&max_weight);
23:  
24:    weight = malloc(sizeof(int)*n);
25:    value = http://www.mamicode.com/malloc(sizeof(int)*n);
26:  
27:    // 动态二维数组并赋初值为0
28:    dp = (int**)malloc(sizeof(int*)*(n+1));
29:    for(i = 0; i <= n; i++)
30:    {
31:      dp[i] = (int*)malloc(sizeof(int)*(max_weight+1));
32:      memset(dp[i],0,(max_weight+1)*sizeof(int));
33:    }
34:    //注意这里是从1开始的不是0,要根据问题定义相一致
35:    for(i = 1; i <= n; i++)
36:        scanf("%d %d",&weight[i],&value[i]);
37:  
38:    for(i = 1; i <= n; i++)
39:    {
40:      for(j = 1; j <= max_weight; j++)
41:        {
42:            if(j < weight[i])
43:                dp[i][j] = dp[i-1][j];
44:            else
45:                dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
46:            printf("%d",dp[i][j]);
47:        }
48:        printf("\n");
49:    }
50:     printf("%d\n",dp[n][max_weight]);
51:  
52:    return 0;
53:  }
54:  

3.1.1 索引的改变

dp[0][j] = 0;
if(j < w[i])
  dp[i+1][j] = dp[i][j];
else
  dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]);

3.1.2 顺序的改变

 1:  dp[n][j] = 0;
 2:  for(i = n-1; i >= 0; i--)
 3:  { 
 4:     for(j = 0; j <= W; i++)
 5:        if(j < w[i])
 6:           dp[i][j] = dp[i+1][j];
 7:        else
 8:           dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
 9:     }
10:  }

该问题的时间复杂度是o(N*W),空间复杂度是o(N*W);时间复杂度已经无法再优化,但是空间复杂度还是可以优化的,用一维数组dp[v]来存放结果,但是内层的重量循环必须 逆序 !!!

首先要知道for(i~n)表示前 i 件物品存入的状态.当用一维数组dp[w]时,dp[w]表示把前i件物品放入容量为w的背包里得到的价值.把i从1～n循环后,最后的dp[w]就是所求的最大值.

现在的状态方程是 dp[w] = max(dp[w],f[w-w[i]]+v[i])

1:  w = 0; dp[w]=0;
2:  for(i = 1; i <= n; i++)
3:      for(j = 1; j <= W; j++)
4:        dp[j] = max(dp[j],dp[w-w[i]]+v[i]);   

思考为什么要逆序?

还是用上面的例子画表格[正序]

分析:

当装第一个物品时:

当j < 2,f[j] = 0; 
当j = 3,f[j] = 3; f[3] = max(f[3]=0; f[3-w[1]]+v[1]=3)
当j = 4,f[j] = 6? f[4] = max(f[4]=0(这是上一行的结果);f[4-w[1]]+v[1]=6);
同理 j=5;f[j]=6;

j = 4/5时,把该背包装了两次,明显不合题意! 所以正向顺序的错误就是出在此处!.

还是用上面的例子画逆序的表格

此时的结果就是正确的了.

上面是用实际的例子来说明这个原因的.实际上也可以从理论上解释.

正序的时候,dp[i][j]变成dp[i][j-w[i]]+v[i]了而不是dp[i-1][j-w[i]+v[i];这样状态方程就改变了.

所以正序情况下dp[v]已经更新了,随着j的增大,dp[j-w[i]]的值不再是上一个状态的值了,相反逆序的情况下就没有改变.

所以逆序能够保证dp[j]和dp[j-w[i]]是上一个状态的,但是正序确实完全背包问题的重要解决方案!

部分的blog中都谈论到这个问题,本人思考的不是很明白;

• 要求背包必须装满

  dp[0]=0; dp[1~W]=-INF;表示当重量容纳值为0时,只接受一个重量为0的物品.
  

• 要求背包可以空下

  dp[0~W]=0; 表示任意容积的背包都有一个有效的解为0;
  

具体解释如下: 初始化的dp数组事实上就是在没有任何物品可以放入背包时的合法状态.

如果要求背包恰好装满,那么此时只有容量为0的背包可能被价值为0的nothing恰好装满.

其他容量的背包均没有合法的解.属于未定义的状态,他们的值就都应该是-INF了.

如果背包并非必须被装满,那么任何容量的背包都有一个合法解"什么都不装",

这个解的价值就是0,所以初始值状态的值也就全部为0了.

待完善…

待完善…