Charm Bracelet一维数组背包_第1行:两个整数,n(物品数量,n≤3500)和m(背包容量,m≤12880)。第2…n+1行:每行

# include <iostream>
using namespace std;
int a[12881] = {0};

//前i个构成w的最大价值 = max{前i-1个构成w-wi的最大价值+vi ， 前i-1个构成w} 
int w[3410] = {0};
int v[3410] = {0};

int main ()
{
	int n, m;
	cin >> n >> m;
	
	for (int i = 0; i < n; i++)
	{
		cin >> w[i] >> v[i];
	}
	//for (int i = 0; i < w[0] && i <= m; i++)
	//{
	//	a[i][0] = 0;
//	}
	//a[w[0]] = v[0];
	// 
	for (int i = 0; i < n; i++)
	{
		for (int j = m; j >= 0; j--)
		{
			if (j - w[i] >= 0)
				a[j] = max(a[j - w[i]] + v[i], a[j]);
			else
				a[j] = a[j];
			/*for (int k = 0; k <= m; k++)
			{
				cout << a[k] << ' ';
			}
			cout << endl;*/
		}
		
	}
	int s = 0;
	for (int i = 0; i <= m; i++)
	{
		if (a[i] > s)
			s = a[i];
	}
	cout << s;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48