完全背包、0-1背包以及多重背包的模板

背包路径的打印
pre[j]=j-cost[i];

背包问题求解时，
//求最大值需满足满条件时则 设f[i]为-INF,f[0]为0
//否则f[i]=0

//求最小值 设f[i]为INF,f[0]=0(不需要分满与否，若求满直接判断即可)

//完全背包

for(int i=1;i<=n;i++){
	for(int j=cost[i];j<=C;j++){
		f[j]=max(f[j-cost[i]]+w[i],f[j]);
	}
}

//0-1背包

for(int i=1; i<=n; i++) {
	for(int j=C; j>=cost[i]; j--) {
		f[j]=max(f[j-cost[i]]+w[i],f[j]);
	}
}

//多重背包

for(int i=1; i<=n; i++) {
	for(int j=sum; j>=0; j--) {
		for(int k=0; k<=c[i]; k++) {
			if(k*a[i]>j)break;
			f[j]=max(f[j],f[j-k*a[i]]+k*w[i]);
		}
	}
}

//多重背包的二进制优化

//多重背包二进制优化
vector<int>V;
vector<int>W;
for (int i = 0; i < n; ++i) {
	scanf("%d%d",&m,&x,&w);
	for (int j = 1; j <= m; j<<=1) {//二进制优化
		V.push_back(j*x);
		W.push_back(j*w);
		m-=j;
	}
	if(m>0) V.push_back(m*x),w.push_back(m*w);//！！！别忘了剩余的数
}
for (int i = 0; i < V.size(); i++) {
	for (int j = C; j >=V[i] ; --j) {
		dp[j]=max(dp[j-V[i]]+W[i],dp[j]);
	}
}

//分组背包（每组最多选择一个）
//i组，每组num[i]个物品，第i组第j个物品的体积为cost[i][j]，价值为w[i][j]

f[0]=0;
for(int i=1;i<=n;i++)
	for(int j=m;j>=0;j--)
		for(int k=1;k<=num[i];k++)
			if(j>=cost[i][k])
				f[j] = max(f[j], f[j-cost[i][k]] + w[i][k]);