219. 完全背包问题（挑战程序设计竞赛）

地址 https://www.papamelon.com/problem/219

有 n 个重量和价值分别为 w_i, v_i 的物品。从这些物品中挑选出总重量不超过 W 的物品，求所有挑选方案中价值总和的最大值。
在这里,每种物品可以挑选任意多件。

输入
输入数据第一行有两个整数 n 和 W，接下来会有 n 行，分别表示 n 个物品的对应的 w_i和 v_i
1≤n≤100
1≤wi≤100
1≤vi≤100
1≤W≤10000
输出
输出一个整数, 表示题目要求的最大价值.
样例 1
输入
3 7
3 4
4 5
2 3
输出
10

解答
动态规划 dp[i][j] 表示前i个物品使用了j的重量下能达到的最大价值

TLE版本代码 时间复杂度是O(n*W^2)

#include <iostream>
#include <memory.h>

using namespace std;

const int N = 1010;
int w[N], v[N];
int W, n;
int dp[N][10010];


int main()
{
	cin >> n >> W;
	memset(dp,0,sizeof dp);
	for (int i = 1; i <= n; i++) {
		cin >> w[i] >> v[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= W; j++) {
			for (int k = 0; k * w[i] <= W; k++) {
				if (j >= k * w[i]) {
					dp[i][j] = max(dp[i][j], dp[i-1][j - k * w[i]] + k * v[i]);
				}
			}
		}
	}

	cout << dp[n][W] << endl;

 
	return 0;
}