背包模板来啦~

01背包：$O(VN)$：$f[i,j]=max(f[i-1,j-need[i]]+value[i])$

完全背包：可以优化到$O(VN)$，$f[i,j]=max(f[i,j-k*need[j]]+k*value[i]) (k \times need[j] < maxW)$

多重背包，$O(V\sum_{i=1}^{N} log_{2}^{n_i})$，和完全背包类似的推法。等下看看单调队列优化。

模板来了~

# include <stdio.h>
# include <string.h>
# include <algorithm>
using namespace std;
const int INF=10000000;
const int Maxn=110,MaxN=100010,MaxW=80010;
int N,W,n,need[MaxN],value[MaxN],f[MaxW];
inline int normalpack() {
	memset(f,0,sizeof(f));
	for (int i=1;i<=N;++i)
		for (int j=W;j>=need[i];--j) 
			f[j] = max(f[j], f[j-need[i]]+value[i]);
	return f[W];
}
inline int zeroonepack() {
	scanf("%d%d",&N,&W);
	for (int i=1;i<=n;++i)
		scanf("%d%d",&need[i],&value[i]);
	return normalpack();	
}
inline int fullpack() {
	scanf("%d%d",&N,&W);
	for (int i=1;i<=N;++i)
		scanf("%d%d",&need[i],&value[i]);
	//memset(f,0,sizeof(f));
	for (int i=1;i<=N;++i) f[i]=-210000;
	for (int i=1;i<=N;++i)
		for (int j=need[i];j<=W;++j) 
			f[j] = max(f[j], f[j-need[i]]+value[i]);
	return f[W];
}
inline int multipack() {
	scanf("%d%d",&n,&W);
	while(n--) {
		int Tneed,Tvalue,Tn,Prefix=1;
		scanf("%d%d%d",&Tn,&Tneed,&Tvalue);
		while(Tn - Prefix >= 0) {
			need[++N]=Tneed*Prefix;
			value[N]=Tvalue*Prefix;
			Tn -= Prefix;
			Prefix <<= 1;
		}
		if(Tn) {
			need[++N]=Tneed*Tn;
			value[N]=Tvalue*Tn;
		}
	}
	/*
	printf("---debug---\n");
	for (int i=1;i<=N;++i)
		printf("No.%d: need:%d, value:%d\n",i,need[i],value[i]);
	printf("---end-of-debug---\n");
	*/
	return normalpack();
}
main() {
	return 0;
}