背包模板

01，多重，完全，分组均采用的是滚动数组的方式写的代码
注意: 如果要改成二维存储形式，当装不下第i个物品时，要去继承上一轮的结果，比如下面的完全背包二维形式

01背包

对于物品而言只能选择1个或者0个两种情况；
dp[j] : 体积为j能获得的最大价值

int V,N;
int w[maxn],v[maxn];
ll dp[maxn];
for(int i = 1;i<=N;i++){
        for(int j = V;j>=w[i];j--){ //因为采用滚动数组，故倒着循环，这样才能保证只选一次
            dp[j] = max(dp[j],dp[j-w[i]] + v[i]);
        }
    }

完全背包

对于物品而言可以无限制选取,也可以不选
dp[j] : 体积为j能获得的最大价值

int N,V;
int w[maxn],v[maxn];//权值、体积
ll dp[maxn];
for(int i = 1;i<=N;i++){
        for(int j = w[i]; j<= V;j++){ //因为采用滚动数组，故正着循环，这样才能选多次
            dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
        }
    }

二维形式

int N,V;
int w[maxn],v[maxn];
ll dp[1010][1010];
for(int i = 1;i<=N;i++){
    for(int j = 1;j<=V;j++){
        if(j - w[i] >= 0) dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]] + v[i]);
        else dp[i][j] = dp[i-1][j]; //不能装下物品i时，就不装，继承上一轮的结果
    }
}

多重背包

对于物品而言最多能够选择从s[i]个,同样也可不选
dp[j] : 体积为j能获得的最大价值

int N,V;
int w[maxn],v[maxn],s[maxn]; // 权值，价值，数量
ll dp[maxn];
int main(){
    cin>>N>>V;
    for(int i = 1;i<=N;i++) scanf("%d %d %d",&w[i],&v[i],&s[i]);
    for(int i = 1;i<=N;i++){
        for(int j = V;j>=w[i];j--){
            for(int k = 1;k<=s[i] && k*w[i]<=j;k++){
                dp[j] = max(dp[j],dp[j - k*w[i]] + k*v[i]);
            }
        }
    }
}

多重背包，二进制拆分优化

将多重背包转换成01背包

int N,V;
int w[maxn],v[maxn],tail;//tail是二进制拆分后的物品数
ll dp[maxn];
int main(){
    cin>>N>>V;
    for(int i = 1;i<=N;i++){
        int ww,vv,ss;scanf("%d %d %d",&ww,&vv,&ss);
        for(int k = 1; k <= ss; k*=2){
            ss -=k;
            w[++tail] = k * ww;
            v[tail] = k * vv;
        }
        if(ss) w[++tail] = ss*ww,v[tail] = ss*vv;
    }
    for(int i = 1;i<=tail;i++){
        for(int j =  V;j>=w[i];j--){
            dp[j] = max(dp[j],dp[j-w[i]] + v[i]);
        }
    }

分组背包

每一组物品中只能选择其中的一个物品
dp[j] : 体积为j能获得的最大价值

int T,N,V;
int G[110][1010],cnt[110];
int w[maxn],v[maxn];
ll dp[maxn];
cin>>V>>N;
    for(int i = 1;i<=N;i++){
        int t;
        scanf("%d %d %d",&w[i],&v[i],&t);
        T = max(T,t);//记录最大组数
        G[t][++cnt[t]] = i; //记录每组每个物品的编号
    }
    for(int i = 1;i<=T;i++){ //组数
        for(int j = V;j>=0;j--){ //体积 ： 因为是倒着循环的，故只会从一组中选一次
            for(int k = 1;k<=cnt[T];k++){//物品
                if(j - w[G[i][k]]>=0) dp[j] = max(dp[j],dp[j - w[G[i][k]]] + v[G[i][k]]);
            }
        }
    }