01背包问题

问题描述：

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

问题特点：每种物品仅有一件，可以选择放或不放。（0：不放 1：放）

基本思路：

这是最基础的背包问题，用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 。 可以压缩空间，f[v]=max{f[v],f[v-c[i]]+w[i]} 　　这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

注意f[v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，最终的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项f[v-1]，这样就可以保证f[N] [V]就是最后的答案。至于为什么这样就可以，由你自己来体会了。

代码实现：

 

#include<stdio.h>

#include<string.h>

#define MINUSINF 0x80000000

#define MAXN 100

#define MAXV 1000

 

int max(int a,int b)

{

    return a>b?a:b;

} 

//n件物品和一个容量为v的背包。第i件物品的费用是c[i]，价值是w[i]，装满与否要求为full

//算法1：经典DP二维数组解法，时间复杂度及空间复杂度均为O(nv) 

int ZeroOnePack1(int n,int v,int c[],int w[],int full)

{

    int i,j;

    int f[MAXN][MAXV];

    if(full){

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

            for(j=0;j<=v;j++) 

                f[i][j]=MINUSINF;

        f[0][0]=0;

    } 

    else {

              memset(f,0,sizeof(f));

       }

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

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

            if(j>=c[i])

                f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);

            else f[i][j]=f[i-1][j];

        }

    }

    if(f[n][v]<0) return -1;

    else return f[n][v];

}

 

//算法2：算法1的一维数组解法，时间复杂度为O(nv)，空间复杂度为O(v)

int ZeroOnePack2(int n,int v,int c[],int w[],int full){

    int i,j;

    int f[MAXV];

    if(full){

        f[0]=0;

        for(i=1;i<=v;i++) 

            f[i]=MINUSINF;

    }

    else{

              memset(f,0,sizeof(f));

       }

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

        for(j=v;j>=0;j--){

            if(j>=c[i])

                f[j]=max(f[j],f[j-c[i]]+w[i]);

        }

    }

    if(f[v]<0) return -1;

    else return f[v];

}

//算法3：算法2的优化，去掉了无必要的判断，时间复杂度为O(nv)，空间复杂度为O(v)

int ZeroOnePack3(int n,int v,int c[],int w[],int full){

    int i,j;

    int f[MAXV];

    if(full){

        f[0]=0;

        for(i=1;i<=v;i++) 

            f[i]=MINUSINF;

    }

    else {

              memset(f,0,sizeof(f));

       }

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

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

            f[j]=max(f[j],f[j-c[i]]+w[i]);

        }

    }

    if(f[v]<0) return -1;

    else return f[v];

}

 

//算法4：算法3的常数优化，在v较大时优势明显，时间复杂度为O(nv)，空间复杂度为O(v)

int ZeroOnePack4(int n,int v,int c[],int w[],int full)

{

    int i,j,sum=0,bound;

    int f[MAXV];

    if(full)

    {

        f[0]=0;

        for(i=1;i<=v;i++) 

            f[i]=MINUSINF;

    }

    else memset(f,0,sizeof(f));

    for(i=1;i<=n;i++) sum+=w[i];

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

    {

        if(i>1) sum-=w[i-1];

        bound=max(v-sum,c[i]);

        for(j=v;j>=bound;j--)

        {

            f[j]=max(f[j],f[j-c[i]]+w[i]);

        }

    }

    if(f[v]<0) return -1;

    else return f[v];

}

 

int main(){

    int i,j;

    int n,v,c[MAXN],w[MAXN];

    while(scanf("%d %d",&n,&v)!=EOF){

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

                     scanf("%d %d",&c[i],&w[i]);

              }

        printf("%d\n",ZeroOnePack1(n,v,c,w,0));

    }

    return 0;

}