背包模板

发表于 | 更新于: | 分类于 ， ， | | 阅读数
字数统计: 193 | 阅读时长 ≈ 1 
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
#include <iostream>
#include<cstdio>
#include<cstring>
#include <algorithm>
using namespace std;
int dp[100009], c[100009], w[100009], m[100009];
int n, M, t;
void zeropack(int cost, int weight)
{
	for (int i = M; i >= cost; i--)
		dp[i] = max(dp[i - cost] + weight, dp[i]);
}
void completepack(int cost, int weight)
{
	for (int i = cost; i <= M; i++)
		dp[i] = max(dp[i - cost] + weight, dp[i]);
}
void multipack(int cost, int weight, int num)
{
	if (num*cost >= M)
	{
		completepack(cost, weight);
		return;
	}
	int k = 1;
	while (k < num)
	{
		zeropack(k*cost, k*weight);
		num -= k;
		k *= 2;
	}

	zeropack(cost*num, weight*num);
}
int main()
{
	while (~scanf("%d%d", &M, &n))
	{
		for (int i = 1; i <= n; i++) { scanf("%d%d", &m[i], &c[i]); w[i] = c[i]; }
		memset(dp, 0, sizeof(dp));
		for (int i = 1; i <= n; i++)
		{
			multipack(c[i], w[i], m[i]);
		}
		printf("%d\n", dp[M]);
	}
	return 0;
}