背包问题模板

　　0/1背包

　　01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2至Wn，与之相对应的价值为P1,P2至Pn。01背包是背包问题中最简单的问题。01背包的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。在01背包问题中，因为每种物品只有一个，对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中，则不需要处理。如果选择将其放入背包中，由于不清楚之前放入的物品占据了多大的空间，需要枚举将这个物品放入背包后可能占据背包空间的所有情况。

#include<bits/stdc++.h>
using namespace std;

const int num = ???;
int t, n, m;// t组数据，n个物品，m背包容量
int v[num], w[num];// wi体积，vi价值
int dp[num];

int ans(){
    //初始化 
    for(int i=0; i<num; ++i)    dp[i] = 0; 
     
    for(int i=1; i<=n; ++i)//第i个物品 
        for(int j=m; j>=w[i]; --j)//j为体积 ！！倒序 
            dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
     
    return dp[m];
} 

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &n, &m);
        for(int i=1; i<=n; ++i)        scanf("%d", v+i);
        for(int i=1; i<=n; ++i)        scanf("%d", w+i);
        printf("%d
", ans());
    }
    return 0;
}

　　完全背包

　　有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

#include<bits/stdc++.h>
using namespace std;

const int num = ???;
int t, n, m;
int w[num], v[num];
int dp[num];

int fullans(){
    //初始化 
    for(int i=0; i<num; ++i)    dp[i] = 0; 
     
    for(int i=1; i<=n; ++i)//第i个物品 
        for(int j=w[i]; j<=m; ++j)//j为体积 ！！顺序 
            dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
     
    return dp[m];    
}

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &n, &m);
        for(int i=1; i<=n; ++i)        scanf("%d", w+i);
        for(int i=1; i<=n; ++i)        scanf("%d", v+i);
        printf("%d
",fullans());
    }
    return 0;
}

　　多重背包

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

d#include<bits/stdc++.h>
using namespace std;

const int N = ???;
int V, m;
int dp[N];
int w[N], num[N];

void mul(int n,int w){
    if(n*w >= V){
        for(int i=w; i<=V; i++)
            dp[i] = max(dp[i], dp[i-w]+w);
        return ;
    }
    int k = 1;
    int nC = n;
    while(k < nC){//01背包，做简单的优化
        for(int i=V; i>=k*w; i--)
            dp[i] = max(dp[i], dp[i-k*w]+k*w);
        nC -= k;
        k *= 2;
    }
    for(int i=V; i>=nC*w; i--)
        dp[i] = max(dp[i], dp[i-nC*w]+nC*w);
}
int main(){
    while(scanf("%d %d", &m, &V) && m && V){
        for(int i=0; i<=V; ++i)        dp[i] = 0;
        for(int i=0; i<m; ++i)        scanf("%d", w+i);
        for(int i=0; i<m; ++i)        scanf("%d", num+i);

    //多重背包    
        for(int i=0; i<m; ++i)
            mul(num[i], w[i]);

        printf("%d
",dp[V]);
    }
    return 0;
}