各种背包模板

把这些背包弄成了模板，比较方便也容易理解
注:这些背包模板都是以函数形式， 每次调用都只解决一个物品。

1.0/1背包

void _0_1bb (int m, int c, int v){//m:背包容量， c:此物品价值， v:此物品体积
    for (int j = m; j >= v; j--){
		dp[j] = max (dp[j], dp[j - v] + c);
	}
}

完全背包

void wqbb (int m, int c, int v){//m:背包容量， c:此物品价值， v:此物品体积
    for (int j = v; j <= m; j++){
		dp[j] = max (dp[j], dp[j - v] + c);
	}
}

多重背包

普通方法

void dcbb (int m, int c, int v, int num){//m:背包容量， c:此物品价值， v:此物品体积 num:此物品数量
	for (int j = m; j >= v; j--){
		for (int i = 1; i <= n; i++){
			if (v * i > j){
				break;
			}
			dp[j] = max (dp[j], dp[j - v * i] + c * i);
		}
	}
}

二进制方法

void dcbb (int m, int c, int v, int num){//m:背包容量， c:此物品价值， v:此物品体积 num:此物品数量
	int tot = 0;
	for (int j = 1; j <= num; j <<= 1){
		sv[++tot] = v * j;
		sc[++tot] = c * j;
		num -= j;
	}
	if (num > 0){
		sv[++tot] = num * v;
		sc[++tot] = num * c;
	}
	for (int i = 1; i <= tot; i++){
		for (int j = m; j >= sv[i]; j--){
			dp[j] = max (dp[j], dp[j - sv[i]] + sc[i]);
		}
	}
}

单调队列优化

void dcbb (int m, int c, int v, int num){
	for (int u = 0; u < v; u++){
		int l = (m - u) / v;
		int h = 0, t = 0;
		s[t++] = make_pair (dp[u], 0);
		for (int i = 1; i <= l; i++){
			while (s[h].second < i - num){
				h++;
			}
			while (s[t - 1].first <= dp[i * v + u] - i * c && t > h){
				t--;
			}
			s[t++] = make_pair (dp[i * v + u] - i * c, i);
			dp[i * v + u] = s[h].first + i * c;
		}
	}
}

分组背包

void fzbb (int m, int num){
	for (int i = m; i >= 0; i--){
		for (int j = 1; j <= num; j++){
			if (v[j] > i){
				continue;
			}
			dp[i] = max (dp[i], dp[i - v[j]] + c[j]);
		}
	}
}

二维费用背包

0/1

void _0_1fzbb (int M, int V, int v, int m, int c){
    for (int i = V; i >= v; i --){
        for (int j = M; j >= m; j--){
            dp[i][j]= max (dp[i][j], dp[i - v][j - m] + c);
        }
    }
}

完全

void wqfzbb (int M, int V, int v, int m, int c){
    for (int i = V; i >= v; i --){
        for (int j = M; j >= m; j--){
            dp[i][j]= max (dp[i][j], dp[i - v][j - m] + c);
        }
    }
}

多重

void dcbb (int M, int V, int c, int m, int v, int num){
	int tot = 0;
	for (int j = 1; j <= num; j <<= 1){
		sv[++tot] = v * j;
		sc[++tot] = c * j;
		sm[++tot] = m * j
		num -= j;
	}
	if (num > 0){
		sv[++tot] = num * v;
		sc[++tot] = num * c;
		sm[++tot] = num * m;
	}
	for (int i = 1; i <= tot; i++){
		for (int j = M; j >= sm[i]; j--){
			for (int k = V; k >= sv[i]; k--)
			dp[j][k] = max (dp[j][k], dp[j - sm[i]][k - sv[i]] + sc[i]);
		}
	}
}

注:这些模板可能是假的可能有些许小问题， 发现请及时指出

使用范例（单调队列优化的多重背包， 其他函数同理）

代码:

#include 
#include 
using namespace std;
#define MAXN 1000
int dp[MAXN + 5];
pair s[MAXN + 5];
void dcbb(int m, int c, int v, int num) {
    for (int u = 0; u < v; u++) {
        int l = (m - u) / v;
        int h = 0, t = 0;
        s[t++] = make_pair(dp[u], 0);
        for (int i = 1; i <= l; i++) {
            while (s[h].second < i - num) {
                h++;
            }
            while (s[t - 1].first <= dp[i * v + u] - i * c && t > h) {
                t--;
            }
            s[t++] = make_pair(dp[i * v + u] - i * c, i);
            dp[i * v + u] = s[h].first + i * c;
        }
    }
}
int main() {
    int n, m;
    scanf("%d %d", &m, &n);
    for (int i = 1; i <= n; i++) {
        int v, c, num;
        scanf("%d %d %d", &v, &c, &num);
        dcbb(m, c, v, num);
    }
    printf("%d", dp[m]);
}