多重背包（C++）暴力

解题思路:

设dp[i][j]的含义是:在背包承重为j的前提下，从前i种物品中选能够得到的最大价值。
如何计算dp[i][j]呢？我们可以将它划分为以下若干部分:
选0个第i种物品：相当于不选第i种物品，对应dp[i-1][j];
选一个第i种物品：对应dp[i - 1][j - v[i]] + w[i];
选两个第i种物品：对应dp[i - 1][j - 2 * v[i]] + 2 * w[i];
.....
上述过程并不会无限进行下去，因为背包的承重是有限的。设第i种物品最多可以选t个，则t = ⌊j / v[i]⌋,
于是得到递推式dp[i][j] = max(0 <= k <= t)(dp[i - 1][j - k * v[i]] + k * w[i];
回顾完全背包问题的解法(暴力)，在背包承重为j的前提下，第i种物品最多能放t = j / w[i]个(这里是整除);
而在01背包问题中，第i种物品只有一个，所以应当取t=min(1,j/w[i])。
由此可知，对于多重背包问题，只需取t=min(s[i],j/w[i])即可。

注意事项:

参考代码:

#include<iostream>
using namespace std;
const int N=3005;

int v[N], w[N], s[N]; // s[]表示第i种物品有s[i]件;
int dp[N][N];

int main()
{
	int n,m; // 物品种数、背包容积;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> v[i] >> w[i] >> s[i];

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			int t = min(s[i], j / v[i]);//t为第i种物品最多能携带的数量; 因为t>=0,所以j/v[i]>=0所以j/k*v[i]>=0;因此，不必像01背包那样讨论下标会不会为负情况;
			for (int k = 0; k <= t; k++)
				dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);//当k==0时，已经包含dp[i-1][j]的情况,由递推式，仅仅dp[i-1][j-k*v[i]]+k*w[i]只是求选第i个且选多少件，并不能找出最大价值，我们要找出此时的dp[i-1][j-k*v[i]]+k*w[i]与上一个dp[i][j]谁更大的情况;

		}
	}

	cout << dp[n][m] << "\n";
	return 0;
}