背包九讲

一 01背包：

一件物品只能放一次

二维动态转移方程 dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])

降低空间复杂度用一维: dp[j] = max(dp[j],dp[j-w[i]]+v[i]), j 从V到0(为了防止数组越界，到w[i])

代码实现：

#include<algorithm>
using namespace std;
const int MAX = 100;
int dp[MAX],w[MAX],v[MAX];
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n ; i++){
        scanf("%d%d",&w[i],&v[i]);
    }
    for(int i = 1; i <= n ; i++){
        for(int j = m; j >= w[i]; j--){
            dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    printf("%d
",dp[m]);
  return 0;
}

二 完全背包：

一件物品能放无限次

二维动态转移方程 dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]]+v[i])

降低空间复杂度用一维：dp[j] = max(dp[j],dp[j-w[i]]+v[i])，不过j从0到V(为了防止数组越界，从w[i]开)

也可以看做m/(w[i])个物品，继续看成01背包问题，价值和重量都放大2^k次

代码实现：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX = 100;
int dp[MAX],w[MAX],v[MAX];
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n ; i++){
        scanf("%d%d",&w[i],&v[i]);
    }
    for(int i = 1; i <= n ; i++){
        for(int j = w[i]; j <= m; j++){
            dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    printf("%d
",dp[m]);
  return 0;
}

三 多重背包：（hdu2191）

限定了每一件物品的适用次数

法一：

结合01背包和完全背包讨论情况

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX = 1111;
int dp[MAX],w[MAX],v[MAX],t[MAX];
int n,m;
void comback(int w,int v)
{
    for(int i = w; i <= n ; i++)
        dp[i] = max(dp[i],dp[i-w]+v);
}
void oneback(int w,int v)
{
    for(int i = n ; i >= w; i--)
        dp[i] = max(dp[i],dp[i-w]+v);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        memset(dp,0,sizeof(dp));
        scanf("%d%d",&n,&m);
        for(int i = 1; i <= m ; i++){
            scanf("%d%d%d",&w[i],&v[i],&t[i]);
            if(w[i]*t[i] >= n) comback(w[i],v[i]);
            else {
                for(int j = 1; j < t[i]; j <<= 1){
                    oneback(j*w[i],j*v[i]);
                    t[i] -= j;
                }
                oneback(t[i]*w[i],t[i]*v[i]);
            }
        }
        printf("%d
",dp[n]);
    }
    return 0;
}

法二：

转化成01背包问题，把每一种放大（二进制）　　　　

主函数型写法

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX = 1111;
int dp[MAX],v[MAX],w[MAX],t[MAX];
int V[MAX],W[MAX];
int main()
{
    int n,m,T;
    scanf("%d",&T);
    while(T--){
        memset(dp,0,sizeof(dp));
        memset(v,0,sizeof(v));
        memset(w,0,sizeof(w));
        memset(t,0,sizeof(t));
        scanf("%d%d",&m,&n);
        int count = 1;
        for(int i = 1; i <= n ; i++){
            scanf("%d%d%d",&w[i],&v[i],&t[i]);
            for(int j = 1; j < t[i]; j <<= 1){
                V[count] = j*v[i];
                W[count] = j*w[i];
                count++;
                t[i] -= j;
            }
                V[count] = t[i]*v[i];
                W[count] = t[i]*w[i];
                count++;
        }
        for(int i = 1; i < count; i++){
            for(int j = m; j >= W[i];j--){
                dp[j] = max(dp[j],dp[j-W[i]]+V[i]);
                }
            }
        printf("%d
",dp[m]);
        }
        return 0;
}

函数型写法（推荐）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX = 50010;
const int inf = 0x3f3f3f3f;
int dp[50010];
int w[110],num[110];
int n,m;
void oneback(int w,int v){
    for(int i =  MAX ; i >= w; i--)
        dp[i] = min(dp[i],dp[i-w]+v);
}
void comback(int w,int v){
    for(int i = MAX+w ; i>= 0; i--)
        dp[i] = min(dp[i],dp[i-w]+v);
}
int multiplepack()
{
    int k ;
    for(int i = 1; i <= MAX; i++)
        dp[i] =inf;
    dp[0] = 0;
    for(int i = 1; i <= 2*n;i ++){
        if( i <= n){
             k = 1;
            while(k < num[i]){
                oneback(k*w[i],k);
                num[i] -= k;
                k*= 2;
            }
            oneback(num[i]*w[i],num[i]);
        }
        else 
            comback(-w[i-n],1);
    }
    if(dp[m] == inf)
        return -1;
    else return dp[m];
}
int main()
{
    while(~scanf("%d%d",&n,&m)){
        memset(dp,0,sizeof(dp));
        for(int i = 1; i <= n ; i++)
            scanf("%d",&w[i]);
        for(int i = 1; i <= n ; i++)
            scanf("%d",&num[i]);
        printf("%d
",multiplepack());
    }
    return 0;
}

四 多重 01 完全混合

五 二维条件的背包

只需要多开一个条件 dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-a[i]][k-b[i]]+w[i])

六 分组的背包问题

多开一个for循环

for(int k = 1; k <= n ;k++){
    for(int j = m; j >= 0 ; j--){
        for(int i = 1 ; i <= a[k]; i++){
            dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
}

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX = 110;
int dp[MAX];
int a[MAX][MAX];
int w[MAX],v[MAX];
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m)&&n&&m){
        memset(dp,0,sizeof(dp));
        memset(a,0,sizeof(a));
        memset(w,0,sizeof(w));
        memset(v,0,sizeof(v));
        for(int i = 1;i <= n ; i++){
            for(int j = 1; j <= m ; j++)
                scanf("%d",&a[i][j]);
        }
        for(int i = 1; i <= n ; i++){
            for(int j = m; j >= 0 ; j--){
                for(int k = 1; k <= j;k++){
                    dp[j] = max(dp[j],dp[j-k]+a[i][k]);
                }
            }
        }
        printf("%d
",dp[m]);
    }
    return 0;
}

七