fzu 2214 Knapsack problem 超大容量01背包

缘起

【1】中已经讲述了01背包dp的解法. 并且给出了复杂度O(N*V)（N是物品数量，V是背包容量）, 但是如果V超大的话, 则复杂度飙升. 则我们需要改换思路. 遂找到了 fzu 2214 Knapsack problem

分析

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
给定n个物品，(ci,wi)为他们的耗费和价值,现在要你解决01背包问题，背包容量是V.

【输入】
多样例, 第一行是样例数T，而对每个样例，第一行是n和V. 然后n行分别是(ci,wi)
1 <= T <= 100
1 <= n <= 500
1 <= V, c[i] <= 10亿
1 <= w[1]+w[2]+...+w[n] <= 5000
所有输入都是正整数

【输出】
对每个样例，输出01背包问题的解

【样例输入】
1
5 15
12 4
2 2
1 1
4 10
1 2

【样例输出】
15

【限制】
Time limit 3000 ms
Memory limit 32768 kB

【来源】
第六届福建省大学生程序设计竞赛-重现赛（感谢承办方华侨大学）

这种问题的特点就是V超大. 但是价值却不大. 所以我们必须要改换dp的意义——

1
经典01背包中的dp[i][j]前i件物品, 容量为j的时候，能产生的最大价值

如果我们改成. 

1
dp[i][j] 为前i件物品能达到价值j所需要的最小容量

那么

1
dp[i][j] = min{dp[i-1][j], c[i]+dp[i-1][j-w[i]]}, 1<=i<=n, w[i]<=j<=5000

滚动数组一波就成为了

1
dp[j] = min{dp[j], c[i]+dp[j-w[i]]}, 1<=i<=n, w[i]<=j<=5000

但是复杂度骤降为 O(5000*N) ，最后得到的dp逆序遍历, 得到第一个dp[j]<=V 的j就是答案.

ac代码

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
49
50
51
52
53
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL

int dp[5005],n,V;

void zo(int c, int w) // 01背包
{
	for (int i = 5004; i>=w; i--)
	{
		if (c+dp[i-w]<dp[i])
		{
			dp[i] = c+dp[i-w];
		}
	}
}

int sz()
{
	for (int i = 5004; ~i; i--)
	{
		if (dp[i]<=V)
		{
			return i;
		}
	}
}

int main() 
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{ 
		memset(dp, 0x3f, sizeof(dp)); // 不选任何物品, 要达到价值0需要背包的最小容量是0, 要达到价值j>0是不可能的——所以赋值为inf,这一点其实在【1】的"关于01背包初始化的细节"中说过
		dp[0] = 0;
		scanf("%d%d", &n, &V);
		int c,w;
		for (int i = 1; i<=n; i++)
		{
			scanf("%d%d", &c, &w);
			zo(c,w);
		}
		printf("%d\n", sz());
	}
	return 0;
}

ac情况

Status Accepted
Time 156ms
Memory 224kB
Length 710
Lang GNU C++
Submitted 2019-08-19 11:41:24
Shared
RemoteRunId 902881

参考

【1】https://yfsyfs.github.io/2019/08/18/%E7%99%BE%E7%BB%83oj-2773-%E9%87%87%E8%8D%AF-01%E8%83%8C%E5%8C%85/