动态规划 ---- 背包问题

一、01背包问题

有n个重量和价值分别为wi，vi 的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和最大的一个。

1:朴素算法

对于每个物品，有可选与不可选两种可能，这取决于背包是否还能装入。若可取，则判断取之前与之后两种选择哪种最终价值总和更大。搜索所有可能。

 1 //输入 
 2 int n,W;
 3 int w[Max_N],v[Max_N];
 4 
 5 // i:物品下标 val:当前背包剩余容量 返回最大总价值 
 6 int rec( int i, int val )
 7 {
 8     if( i>=n  ) 
 9     {//没有剩余物品 
10         return 0;
11     }
12     
13     int res = 0;
14     if( w[i]>val )
15     {//物品无法装入背包 
16         res = rec( i+1, val ); //继续选择下一个 
17     }
18     else
19     {//物品可以装入,选择两种情况下总价值最大的 
20         res = max( rec(i+1,val), rec(i+1,val-w[i])+v[i] );
21     }
22     return res;
23 }
24 
25 void solve()
26 {
27   printf("%d
",rec(0,W));
28 }

View Code

这种方法搜索深度为n,每次都有两个分支，最终时间复杂度为O(2^n)

2.记忆化搜索

观察递归搜索树可以发现有重复搜索的地方，加入dp[][]数组保存中间结果(剪枝)。

 1 int dp[Max_N+1][Max_W+1]; //记忆化数组 
 2 
 3 // i:物品下标 val:当前背包剩余容量 返回最大总价值 
 4 int rec( int i, int val )
 5 {
 6     if( dp[i][val]>=0 )
 7     {//避免重复计算(剪枝) 
 8         return dp[i][val];
 9     }
10 
11     if( i>=n  ) 
12     {//没有剩余物品 
13         return dp[i][val] = 0;
14     }
15     
16     int res = 0;
17     if( w[i]>val )
18     {//物品无法装入背包 
19         res = rec( i+1, val ); //继续选择下一个 
20     }
21     else
22     {//物品可以装入,选择两种情况下总价值最大的 
23         res = max( rec(i+1,val), rec(i+1,val-w[i])+v[i] );
24     }
25     return dp[i][val] = res;
26 }
27 
28 void solve()
29 {
30     //用负数表示尚未计算过 
31     memset(dp,-1,sizeof(dp));
32     printf("%d
",rec(0,W));
33 }

View Code

对于相同参数只会被调用一次，参数的组合只有 nW 种，且每次函数只有两次调用递归，所以时间复杂度下降为O(nW)。这种方法称为记忆化搜索。

3.动态规划

结合搜索函数和相对应的记忆化数组:

rec(i,j) = rec( i+1, j ) 　　　　　　　　　 j<w[ i ]　　　　dp[ i ][ j ] = dp[ i+1][ j ] 　　　　　　　　　　　　　　　 j<w[ i ]

max( rec(i+1,j), rec(i+1, j-w[ i ] ) + v[i] ) otherwise 　　 = max( dp[ i+1 ][ j ] , dp[ i+1 ][ j - w[ i ] ] + v[ i ] ) otherwise

可以不用写函数，从初始dp[ n ][ j ] = 0 状态利用上递推式将各项值计算出来，用二重循环即可解决。

这里及以下所有dp数组均为全局变量，当初始值为0时没有进行初始化。

 1 int dp[Max_N+1][Max_W+1]; //DP数组 
 2 
 3 void solve()
 4 {
 5     for( int i=n-1; i>=0; i-- )
 6     {
 7         for( int j=0; j<=W; j++ )
 8         {
 9             if( j<w[i] )
10             {
11                 dp[i][j] = dp[i+1][j];
12             }
13             else
14             {
15                 dp[i][j] = max( dp[i+1][j], dp[i+1][j-w[i]]+v[i] );
16             }
17         }
18     }
19     printf("%d
",dp[0][W]); //<-->rec(0,W)
20 }

View Code

这时的dp[ i ][ j ] 可以理解为从第i件物品开始选背包容量为j的最大总价值。

若将dp[ i ][ j ] 理解为从第0见开始选到第i件且背包容量为j的最大价值，有第二种递推式。

 1 int dp[Max_N+1][Max_W+1]; //DP数组 
 2 
 3 void solve()
 4 {
 5     //dp[0][j] = 0
 6     for( int i=0; i<n; i++ )
 7     {
 8         for( int j=0; j<=W; j++ )
 9         {
10             if( j<w[i] )
11             {
12                 dp[i+1][j] = dp[i][j];
13             }
14             else
15             {
16                 dp[i+1][j] = max( dp[i][j], dp[i][j-w[i]]+v[i] );
17             }
18         }
19     }
20     printf("%d
",dp[n][W]);
21 }

View Code

利用一维数组:若我们需要的仅仅是最终结果，观察到dp[ i+1 ][ j ]仅与其上一个物品时dp[ i ][ j ]有关，所以可以重复利用一维数组完成递推式。

 1 int dp[Max_W+1]; //一维DP数组 
 2 
 3 void solve()
 4 {
 5     for( int i=0; i<n; i++ )
 6     {
 7         for( int j=W; j>=w[i]; j-- )
 8         {
 9             dp[j] = max( dp[j], dp[j-w[i]]);
10         }
11     }
12     printf("%d
",dp[W]);
13 }

View Code

这时原来的dp[i]的i可以认为是上一次循环时产生的dp值，即这一维在i循环种被隐去了。 (我也还没十分了解)

二、完全背包问题