背包问题

cite:https://www.jianshu.com/p/d9a0624c05e7
W是最大能装的重量，w[i]是第i件物品的重量， v[i]是价值
循环中k是装的数量，j是当前的重量，i是第i件物品

转移方程：dp[j] = max(kv[i] + dp[j - kw[i]], dp[j])
当k=1就是01背包

01背包

for(int i=0; i<w.size(); ++i){
	for(int j=W; i>=w[i]; --j){
		dp[j] = max(dp[j], v[i]+dp[j-w[i]]);
	}
}

完全背包

for(int i=0; i<w.size(); ++i){
	for(int j=w[i]; i<W; ++j){
		dp[j] = max(dp[j], v[i]+dp[j-w[i]]);
	}
}

多重背包

for(int i=0; i<w.size(); ++i){
	for(int j=W; j>=w[i]; --j){
		int cur = min(j/w[i], nums[i]); //nums[i]是最大数量 ， cur是第i件物品在容量j的背包里能装的最大数量
		for(int k=0; k<=cur; ++j){
			dp[j] = max(dp[j], k*v[i]+dp[j-k*w[i]]);
		}
	}
}