完全背包问题（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];
参考文献：https://blog.csdn.net/raelum/article/details/128996521作者：Lareges

注意事项:

参考代码:

#includeusing namespace std;

const int N = 1008;

int v[N], w[N];//v[i]表示第i个物品的价值,w[i]表示第i个物品的重量;
int dp[N][N]; // 创建dp数组;

int main()
{
	int n, m; // 物品数量、背包最大承重;
	cin >> m >> n;
	for (int i = 1; i >w[i] >> v[i];

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			int t = j / w[i]; // t为第i种物品最多能携带的数量;
			for (int k = 0; k <= t; k++)
				dp[i][j] = max(dp[i-1][j], dp[i - 1][j - k * w[i]] + k * v[i]);
		}
	}
	cout << "max=" << dp[n][m] << "\n";
	return 0;
}