HDOJ-2191【多重背包】

题目链接HDU-2191

题目描述

急!灾区的食物依然短缺!
为了挽救灾区同胞的生命,心系灾区同胞的你准备自己采购一些粮食支援灾区,现在假设你一共有资金n元,而市场有m种大米,每种大米都是袋装产品,其价格不等,并且只能整袋购买。
请问:你用有限的资金最多能采购多少公斤粮食呢?

Input
输入数据首先包含一个正整数C,表示有C组测试用例,每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类,然后是m行数据,每行包含3个数p,h和c(1<=p<=20,1<=h<=200,1<=c<=20),分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。

Output
对于每组测试数据,请输出能够购买大米的最多重量,你可以假设经费买不光所有的大米,并且经费你可以不用完。每个实例的输出占一行。

Sample Input
1
8 2
2 100 4
4 100 2

Sample Output
400

思路

这道题类似于01背包,但由于规定每种物品的种类数有上限,所以是一道多重背包问题。
这里列举一下三种背包的不同之处;
01背包 每一种物品只有选择和不选两种状态;
完全背包每一种物品可以选择0,1,2,3,4….n件; n w[i] <= T, 就是最多选择 重量 个数 小于等于 容量个物品;
多重背包规定了每种物品的选取上限,可以取0,1,2,3….MAX(i)件;

这是只说一下多重背包,多重背包可以拆分为多个01背包问题进行解决,即一个物品如果可以选择多个,那么我们可以将这个物品拆分为max(i)个物品,每一种选择都当做一种新的物品来看待,这样子就可以解决多重背包;

朴素的多重背包算法:

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
#include <bits/stdc++.h>
using namespace std;

#define long long long
#define MAX_N 100010
#define INF 0x3f3f3f3f

int dp[MAX_N];
int v[110], w[110], k[110];

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int t;
cin >> t;
while(t--)
{
memset(dp, 0, sizeof(dp));
int T, n;
cin >> T >> n;
for(int i = 1; i <= n; i++)
{
cin >> w[i] >> v[i] >> k[i];
}
for(int i = 1; i <= n; i++)//枚举每个物品
{
for(int j = 1; j <= k[i]; j++)//将第i种物品拆分为 k[i]种不同的物品
{
for(int p = T; p >= w[i]; p--)//状态转移
{
dp[p] = max(dp[p], dp[p - w[i]] + v[i]);
}
}
}
cout << dp[T] << endl;
}
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
#include <bits/stdc++.h>
using namespace std;

#define long long long
#define MAX_N 100010
#define INF 0x3f3f3f3f

int dp[MAX_N];
int v[110], w[110], k[110];

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int t;
cin >> t;
while(t--)
{
memset(dp, 0, sizeof(dp));
int T, n;
cin >> T >> n;
for(int i = 1; i <= n; i++)
{
cin >> w[i] >> v[i] >> k[i];
}
for(int i = 1; i <= n; i++)//枚举每个物品
{
for(int j = T; j >= 0; j--)// 状态转移
{
for(int p = 1; p <= k[i] && p * w[i] <= j; p++)// 枚举选择的数量
{
dp[j] = max(dp[j], dp[j - p * w[i]] + p * v[i]);
}
}
}
cout << dp[T] << endl;
}
return 0;
}

因为这到题的数据范围很小,所以用朴素的算法也可以通过;但是当数据范围变大的时候,朴素的算法表现的就不太好了。所以我们得做一些优化;
我们可以用二进制进行优化。 比如 某一个物品最多可以选取13个, 我们朴素的做法是 将其拆分为13个原物品, 然后进行01背包; 这个过程我们可以优化, 试想 1, 2, 4, 6。是否可以枚举出1-13所有的状态呢? 答案是肯定的,1-13无论是哪个状态,我们都可以对1,2,4,6这4个状态进行合并得到;这样就降低了原复杂度。 原来枚举O(n),现在只需要枚举O(logN),大大降低了时间复杂度;OK, 写一下代码;

二进制优化代码:

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
#include <bits/stdc++.h>
using namespace std;

#define long long long
#define MAX_N 100010
#define INF 0x3f3f3f3f

int dp[MAX_N];
int v[110], w[110], k[110];

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int t;
cin >> t;
while(t--)
{
memset(dp, 0, sizeof(dp));
int T, n;
cin >> T >> n;
for(int i = 1; i <= n; i++)
{
cin >> w[i] >> v[i] >> k[i];
}
for(int i = 1; i <= n; i++)//枚举每一种物品
{
int tmp = k[i];
for(int p = 1; p <= tmp; p <<= 1)//二进制拆分
{
for(int j = T; j >= p * w[i]; j--)//状态转移
{
dp[j] = max(dp[j], dp[j - p * w[i]] + p * v[i]);
}
tmp -= p;
}
if(tmp)
{
for(int j = T; j >= tmp * w[i]; j--)
{
dp[j] = max(dp[j], dp[j - tmp * w[i]] + tmp * v[i]);
}
}
}
cout << dp[T] << endl;
}
return 0;
}
-------------本文结束,感谢您的阅读!-------------