DP- 01背包问题

这个01背包，理解了一天才勉强懂点，写个博客（推荐 http://blog.csdn.net/insistgogo/article/details/8579597）

题目：

　　有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

分析一下：

　　面对一件物品，我有两种选择，放或者不放，如果不放，则最大价值是前 n - 1 件物品放入容量为 j 的背包，如果放，则最大价值是将前 n - 1 件物品放入剩余容量为 j - c[j] ，此时的

价值是前 n - 1 件物品放入剩余容量为 v - c[ j ] 的价值加上放入该物品的价值 .......一直此过程，最后的最大价值即是 c[ n ] [ v ] 。

（偷一个图）：

　　要怎样去实现这个代码呢？先用最好的理解的二维数组去解决这个问题，两个维度分别存的是 物品的个数以及 当前背包的总容量 ，因为我第一层 for 是从遍历所有的物品，即面对某个物品，第二层 for 我是遍历体积，每次让体积 + 1 ，这样就会产生一种什么效果呢？在面对每一个物品时，我所有的体积都去试一下，这个过程从最终的意义上考虑实际都是在为最后背包容量满的时候服务，这个过程也就叫做构建最优子结构的过程，并且当前产生的结果，对后面不会有任何影响，也就是无后效性。

　　（关于这个代码，我感觉有一个地方很精髓，就是当面对一号物品时，我的状态转移方程考虑的是前 i - 1 个物品，即没有物品的时候，此时我建立的数组就可以在 i = 0 的位置留出地方，并且借助 memset 将这些位置都给 0 ）

　　（还有这个的背包容量也可以从 V 开始遍历直到 1 结束，则会打出另一张表）

代码示例：

// 感觉 DP 中的背包问题 就是一个制作表格的过程

// 所制作的表的大小是 n * v 

#include <iostream>

#include <algorithm>

using namespace std ;

int dp[10][500] ;   // 定义为全局变量 会被初始化为 0

int weight[15] ;

int value[15] ;

int main ( ) {

    int n , v ;

    cin >> n >> v ;

    for ( int i = 1 ; i <= n ; i++ ) {

        cin >> weight[i] >> value[i] ;

    }

    for ( int i = 1 ; i <= n ; i++ ) {

        for ( int j = 1 ; j <= v ; j++ ) {

            if ( weight[i] <= j )

                dp[i][j] = max ( dp[i-1][j] , dp[i-1][j-weight[i]] + value[i] ) ;

            else

                dp[i][j] = dp[i-1][j] ; // 如果当前面对此物品背包中不能再放东西 ，但表的这一栏又不能空 ，

                                        // 所以填的数 是这个体积下，没有此物品的体积

        }

    }

    cout << dp[n][v] << endl ;

    return 0 ;

}

二 . 优化空间复杂度

　　用二维数组去写的话，复杂度为 O （n*v），在数据大的时候直接超内存，所以可以借助一维数组，将复杂度优化为 O （n）

　　贴上我的代码：

// 感觉 DP 中的背包问题 就是一个制作表格的过程

// 所制作的表的大小是 n * v

#include <iostream>

#include <algorithm>

using namespace std ;

int dp[1500] ;   // 定义为全局变量 会被初始化为 0

int weight[15] ;

int value[15] ;

int main ( ) {

    int n , v ;

    cin >> n >> v ;

    for ( int i = 1 ; i <= n ; i++ ) {

        cin >> weight[i] >> value[i] ;

    }

    for ( int i = 1 ; i <= n ; i++ ) {

        for ( int j = v ; j >= 1 ; j-- ) {

            if ( weight[i] <= j )

                dp[j] = max ( dp[j] , dp[j-weight[i]] + value[i] ) ;  // 当面对一个物品时 ， 此时数组所对应的即是前 i - 1 的价值

        }

    }

    cout << dp[v] << endl ; 

    return 0 ;

}

// 用一维数组做，感觉和数字三角形的题很像，从底下递推。此背包问题就是，在面对每个物品时，不断地更新数组中的数据，并且在面对每个物品时，其体积是从 V 到 1 递推

// 用一维数组做，当面对一个物品，在这个位置上，数组所存的数即是在该体积下，前 i - 1 件物品的最大价值

有一个问题：体积为什么要是逆序递推呢？

然后附上我程序的运行结果：

三 . 初始化的细节问题

　　在最优解得背包问题，有两种问法；

　1 . 在不超过背包容量时，如何装会获得最大价值？

　2 .当背包恰好装满时，获得的最大价值是多少？

　　两种问法的唯一区别就在于就在于背包是否装满，这两种问法的实现仅仅区别于对数组元素的初始化。

　　初始化 f 数组就表示，在没有放入任何物品时背包的合法状态。

　　对于恰好装满的情况，我应对此二维数组的 dp[ i ] [ 0 ] 初始化为 0 ，因为我在面对一个物品时，我此时背包的容量为 0 ，不能再放任何东西，即为恰好装满的时候，将此 dp 数组其余位置全部初始为负无穷，其余过程全部同上 ... 最后时输出恰好的最优解即 dp[ n ][ v ] 。

　　对于不超过背包容量的情况，我只需要将数组中的元素全部初始为 0 。如果背包并非要全部装满，那么任何背包都有一个合法解，即什么也不装。

恰好装满的二维数组代码：

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std ;

int dp[10][500] ;   // 定义为全局变量 会被初始化为 0

int weight[15] ;

int value[15] ;

int main ( ) {

    int n , v ;

    int i , j;

    cin >> n >> v ;

    memset ( dp , 0x8f , sizeof(dp) ) ;  // 将数组全部元素初始化为 负无穷

    for ( i = 0 ; i <= n ; i++ ) {

        dp[i][0] = 0 ;

    }

    for ( i = 1 ; i <= n ; i++ ) {

        cin >> weight[i] >> value[i] ;

    }

    for ( i = 1 ; i <= n ; i++ ) {

        for ( j = 1 ; j <= v ; j++ ) {

            if ( weight[i] <= j ) {

                dp[i][j] = max ( dp[i-1][j] , dp[i-1][j-weight[i]] + value[i] ) ;

            }

            else

                dp[i][j] = dp[i-1][j] ;

        }

    }

    cout << dp[n][v] << endl ;

    return 0 ;

}

恰好装满的一维数组的代码：

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std ;

int dp[1500] ;   // 定义为全局变量 会被初始化为 0

int weight[15] ;

int value[15] ;

int main ( ) {

    int n , v ;

    memset ( dp , 0x8f , sizeof(dp) ) ;

    dp[0] = 0 ;

    cin >> n >> v ;

    for ( int i = 1 ; i <= n ; i++ ) {

        cin >> weight[i] >> value[i] ;

    }

    for ( int i = 1 ; i <= n ; i++ ) {

        for ( int j = v ; j >= weight[i] ; j-- ) {

            dp[j] = max ( dp[j] , dp[j-weight[i]] + value[i] ) ;  // 当面对一个物品时 ， 此时数组所对应的即是前 i - 1 的价值

        }

    }

    cout << dp[v] << endl ;

    return 0 ;

}

附上利用机器打得表：

四 . 一个常数的优化

　　在用一维数组，做背包问题时，背包容量是从 v 到 1 遍历，但实际上只需要遍历到 weight[ i ] 。

代码示例：

#include <iostream>

#include <algorithm>

using namespace std ;

int dp[1500] ;   // 定义为全局变量 会被初始化为 0

int weight[15] ;

int value[15] ;

int main ( ) {

    int n , v ;

    cin >> n >> v ;

    for ( int i = 1 ; i <= n ; i++ ) {

        cin >> weight[i] >> value[i] ;

    }

    for ( int i = 1 ; i <= n ; i++ ) {

        for ( int j = v ; j >= weight[i] ; j-- ) {    //////////  修改处

            dp[j] = max ( dp[j] , dp[j-weight[i]] + value[i] ) ;  // 当面对一个物品时 ， 此时数组所对应的即是前 i - 1 的价值

        }

    }

    cout << dp[v] << endl ;

    return 0 ;

}

背包的路径输出（板子）

int n,m;

int v[MAX],w[MAX];

int dp[MAX];

bool path[MAX][MAX];

int V;

void solve()

{

    memset(dp,0,sizeof(dp));

   memset(path,false,sizeof(path));

   for(int i=0;i<n;i++)

   {

       for(int j=V;j>=w[i];j--)

        if(dp[j-w[i]]+v[i]>dp[j])

        {

            dp[j]=dp[j-w[i]]+v[i];

            path[i][j]=true;//cout<<i<<j<<endl;

        }

   }

   cout<<dp[V]<<endl;

   int ans[MAX];

   int k=0;

   for(int i=n-1;i>=0;i--)

   {

       if(path[i][V]){

        ans[++k]=i;

        V-=w[i];

       }

   }

   //输出所选择的物品

   for(int i=k;i>0;i--)

     cout<<ans[i]<<endl;

}

巴特西

DP- 01背包问题

最新文章

热门文章