dp-完全背包

( 推荐： http://blog.csdn.net/insistgogo/article/details/11081025 )

问题描述：已知一个容量为 V 的背包和 N 件物品，第 i 件物品的价值是 value[ i ] 体重为 weight[ i ] 。

条件：每件物品有无限多个，能放多少就放多少。

问题：在不超过背包容量的前提下，问最多能获得的最大收益。

基本思路 : 直接扩展01背包

　　区别于 01背包，完全背包中的物品可以放入0件、 1件、 2件 ... ，所以就可以写这样的状态转移方程。

dp[j] = max ( dp[j] , dp[j-k*weight[i]]+k*value[i] ) ;  k <= v / weight[i]

　　这样写的意思是，同 01背包一样，我遍历所有物品，在每个物品下遍历所有体积，完全背包只需要在加一点就是在每种物品的每个体积下，我在遍历所有可能该种物品可以放多少个。

给出完整的代码：

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std ;

#define Max(a,b) a>b?a:b

int weight[10] ;

int value[10] ;

int dp[100] ;

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-- ) {

            for ( int k = 1 ; k <= v/weight[i] ; k++ ) {

                dp[j] = Max ( dp[j] , dp[j-k*weight[i]]+k*value[i] ) ;

            }

        }

    }

    cout <<dp[v] ;

    return 0 ;

}

代码优化：

　　完全背包有一种很简单有效的优化，两件物品重量为 we[i] , we[j] ，价值为va[i] , va[j] 。若we[i] < w[j] ，并且 va[i] > va[j] ，则将物品 j 去掉，不用考虑。但我觉得这样做的话还是不太好，虽然没在网上找到反例。

转化为01背包求解：

　　对于每件物品，背包最多能装的件数是 v / weight[i] ，因此就可以进行一个预处理，增加所有可以增加的物品，直到每种物品的数量都达到 v / weight[i] 。此时在看这个问题，就可以完全转变为 01 背包。

时间复杂度的分析：O（NNew*V），其中V表示扩展前背包容量，NNew表示扩展后物品的个数，NNew = Σ(V/Weight[i](向下取整))

对物品拆分，拆成 2 进制的形势

　　具体思路：把第i种物品拆成费用为weight[i]*2^k、价值为w[i]*2^k的若干件物品，其中k满足weight[i]*2^k<=V。

　　二进制思想：因为不管最优策略选几件第 i 件物品，总可以表示成若干个 2^k 的和。

盗的代码，表示还不会写：

    #include <iostream>

    #include <vector>

    #include <assert.h>

    using namespace std;

    /*

    f[v]:表示第i件物品放入容量为v的背包后，获得的最大容量

    f[v] = max(f[v],f[v - weight[i]] + value[i]);

    初始条件：f[0] = 0;

    */  

    const int N = 3;

    const int V = 20;//5

    int weight[N + 1] = {0,3,2,2};

    int Value[N + 1] = {0,5,10,20};  

    int NNew = 0;

    vector<int> weightVector;

    vector<int> Valuevector;

    int f[V + 1] = {0};

    /*拆分物品*/

    void SplitItem()

    {

        //从1开始

        weightVector.push_back(0);

        Valuevector.push_back(0);

        //开始拆分

        int nPower = 1;

        for (int i = 1;i <= N;i++)

        {

            nPower = 1;

            while (nPower * weight[i] <= V)

            {

                weightVector.push_back(nPower * weight[i]);

                Valuevector.push_back(nPower * Value[i]);

                nPower <<= 1;

            }

        }

    }  

    int Completeknapsack()

    {

        //拆分物品

        SplitItem();

        //转化为01背包处理

        NNew = weightVector.size() - 1;//多加了一个0，要减去  

        for (int i = 1;i <= NNew;i++)//物品个数变化

        {

            for (int v = V;v >= weightVector[i];v--)//背包容量仍是V

            {

                f[v] = max(f[v],f[v - weightVector[i]] + Valuevector[i]);

            }

        }  

        return f[NNew];

    }

    int main()

    {

        cout<<Completeknapsack()<<endl;

        system("pause");

        return 1;

    }

（N * V 的算法）

　　在完全背包中，v变化的区间是顺序循环的原因：完全背包的特点是每种物品可选无限件，在求解加选第i种物品带来的收益f[i][v]时，在状态f[i][v-c[i]]中已经尽可能多的放入物品i了，此时在f[i][v-c[i]]的基础上，我们可以再次放入一件物品i，此时也是在不超过背包容量的基础下，尽可能多的放入物品i。

　　代码示例：

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std ;

#define Max(a,b) a>b?a:b

int weight[10] ;

int value[10] ;

int dp[100] ;

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 = weight[i] ; j <= v ; j++ ) {

            dp[j] = Max ( dp[j] , dp[j-weight[i]]+value[i] ) ;  // 对于每件物品 ， 在不超背包体积的前提下 ， 尽可能多的放

        }

    }

    cout <<dp[v] ;

    return 0 ;

}

巴特西

dp-完全背包

最新文章

热门文章