多重背包

有一个体积为V的背包，有m种物品，每种物品有体积和价值，且数量一定。求背包能装下的最大价值。

输入描述:

第一行两个整数V和m。
接下来m行，每行3个整数，表示第i种物品的数量、体积和价值。
V<=10^4, m<=500，个数、体积、价值不超过1000。

输出描述:

输出一个整数，表示背包能装下的最大价值。

示例1
输入

10 4
2 3 2
2 4 3
1 2 2
4 5 3

输出
8

duochongbeibao1.cppview raw

#include <iostream>
using namespace std;

const int N = 510;
const int M = 10010;
int A[N];
int m, V;
int dp[M];
int main(){
    scanf("%d%d", &V, &m);
    int x, y, z;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d", &x, &y, &z);
        for(int j=V;j>=0;j--){
            for(int k=0;k<=x;k++)
                if(j>=k*y)
                    dp[j] = max(dp[j], dp[j-k*y] + k*z);
        }
    }
    printf("%d\n", dp[V]);
    return 0;
}

duochongbeibao2.cppview raw

#include <iostream>
using namespace std;

const int N = 510;
const int M = 10010;
int A[N];
int m, V;
int dp[M];
int main(){
    scanf("%d%d", &V, &m);
    int x, y, z;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d", &x, &y, &z);
        int k = 0;
        for(int j=1; j<=x; j*=2){
            A[k++] = j;
            x-=j;
        }
        if(x) A[k++] = x;

// note: m must be at the outerloop
        for(int m=0;m<k;m++)
            for(int j=V;j>=A[m]*y; j--){
                dp[j] = max(dp[j], dp[j-A[m]*y] + A[m]*z);
            }
    }
    printf("%d\n", dp[V]);
    return 0;
}

duochongbeibao3.cppview raw

// dp[k*y+j] = max(dp[t*y+j] + (k-t)*z)
// dp[k*y+j] = max(dp[t*y+j] - t*z) + k*z

#include <iostream>
using namespace std;

const int N = 510;
const int M = 10010;
int m, V;
int dp[M];

struct node{
    int cnt, val;
}Q[M];

int main(){
    scanf("%d%d", &V, &m);
    int x, y, z;
    for(int i=1;i<=m;i++) {
        scanf("%d%d%d", &x, &y, &z);

        for(int j=0;j<y;j++) {
            int L = 0, R = -1;
            for (int k = 0; k * y + j <= V; k++) {
                node tmp = (node){k, dp[k*y+j] - k*z}; //easy to forget
                while(L<=R && Q[R].val<=tmp.val) R--;
                while(L<=R && tmp.cnt - Q[L].cnt > x ) L++;
                Q[++R] = tmp;
                dp[k*y+j] = max(dp[k*y+j], Q[L].val + k*z);

            }
        }

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

duochongbeibao3.5.cppview raw

#include <iostream>
using namespace std;

const int N = 100005;
int dp[N][N];

struct node{
    int cnt, val;
}Q[N];

int main(){
    int V, n, x, y, z;
    cin>>V>>n;
    for(int i=1;i<=n;i++) {
        scanf("%d%d%d", &x, &y, &z);
        for(int j=0;j<x;j++){
            int L = 0, R = -1;
            for(int k=0;k*x+j<=V; k++){
                node tmp = (node){k,dp[i-1][k*x+j] - k*y};
                while(R>=L && tmp.val >= Q[R].val)R--;
                while(R>=L && tmp.cnt - Q[L].cnt>z) L++;
                Q[++R] = tmp;
                dp[i][k*x+j] = Q[L].val + k*y;
            }
        }
        for(int j=0;j<=V;j++) dp[i][j] = max(dp[i-1][j], dp[i][j]);
    }
    return 0;
}

duochongbeibao4.cppview raw

#include <bits/stdc++.h>
using namespace std;
#define M 10005
int Q[M],Q2[M],dp[M];
int main() {
//  dp[cur][k*d+i]-k*val[i] = Max(dp[!cur][j*d+i]-j*val[i]);
    int n,v;
    scanf("%d%d",&v,&n);
    for(int i=1,num,ct,val; i<=n; i++) {
        scanf("%d%d%d",&num,&ct,&val);
        for(int j=0; j<ct; j++) {
            int head = 1,tail = 0;
            for(int k=0; k*ct+j<=v; k++) {
                int res = dp[k*ct+j]-k*val;
                while(head <= tail && k-Q2[head] > num) head ++;
                while(head <= tail && res >= Q[tail]) tail--;
                Q[++tail] = res,Q2[tail] = k;
                dp[k*ct+j] = Q[head]+k*val;
            }
        }
    }
    printf("%d\n",dp[v]);
    return 0;
}