poj-1014 多重背包问题

130 阅读 0 评论 86 点赞

我是靠谱客的博主乐观蜗牛，这篇文章主要介绍poj-1014 多重背包问题，现在分享给大家，希望可以做个参考。

Dividing

题意：有一堆大理石，每个石头的价值在1-6之间，每种价格的石头有多个。现在要求将这堆石头分成两份，使得两份的总价值相同，回答是否存在一种方法将可以实现划分。

这是一道多重背包问题，多重背包问题的做法可以是先将它转化为01背包，再用01背包问题的方法继续求解。转化的思路是，将一个价格下的几件物品，组合成多个价格下个一件物品。比如价格2下原来有7件物品(二进制111)，可以分为有1件价格1的物品(001)，1件价格2的物品(010)，1件价格4的物品(100)，可以看出这里用到了二进制的操作。这么操作能够实现每种物品只有一个，只有1拿和0不拿两种情况。且可以组合成原多重背包时的任意组合。

程序中，t[i]表示有价值i的大理石数量，现在要把他分成编号1-count-1的大理石w[i]记录编号i的大理石的价值，转化后，每个编号下的物品只有一个。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i=1;i<=6;i++)
{
int c=1;
while(t[i]-c>0)
{
w[count]=c*i;
t[i]-=c;
c=c<<1;
count ++;
}
w[count]=t[i]*i;
count++;
}

本题与常见的01背包略有不同的是，本题没有物品的体积，所以可以当作物品的体积和价值一样来做。状态转移方程就是，dp[i][j] = MAX( dp[i][j-w[i]]+w[i] , dp[i-1][j] )，做题时再把dp数组压缩成一维，便有了如下的程序

复制代码

1
2
3
4
5
6
7
for(int i=1;i<=count-1;i++)
{
for(int j=sum;j>=w[i];j--)
{
dp[j] = max(dp[j],dp[j-w[i]]+w[i]);
}
}

看到了博客经典背包问题 01背包+完全背包+多重背包写得不错，引用一下，可以当作模板的两个代码

01 背包

有n 种不同的物品，每个物品有两个属性，size 体积，value 价值，现在给一个容量为 w 的背包，问最多可带走多少价值的物品。

复制代码

1
2
3
4
5
6
int f[w+1];
//f[x] 表示背包容量为x 时的最大价值
for (int i=0; i<n; i++)
for (int j=w; j>=size[i]; j--)
f[j] = max(f[j], f[j-size[i]]+value[i]);

完全背包

如果物品不计件数，就是每个物品不只一件的话，稍微改下即可

复制代码

1
2
3
for (int i=0; i<n; i++)
for (int j=size[i]; j<=w; j++)
f[j] = max(f[j], f[j-size[i]]+value[i]);

最后是我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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
int t[10],dp[140010],w[140010];
int DP_fun(int sum)
{
memset(dp,0,sizeof(dp));
int count = 1;
for(int i=1;i<=6;i++)
{
int c=1;
while(t[i]-c>0)
{
w[count]=c*i;
t[i]-=c;
c=c<<1;
count ++;
}
w[count]=t[i]*i;
count++;
}
for(int i=1;i<=count-1;i++)
{
for(int j=sum;j>=w[i];j--)
{
dp[j] = max(dp[j],dp[j-w[i]]+w[i]);
}
}
return dp[sum];
}
int main()
{
for(int ID=1;1;ID++)
{
int flag = 0;
int sum=0;
for(int i=1;i<=6;i++)
{
cin >> t[i];
if(t[i]>0)
{
flag = 1;
sum += t[i]*i;
}
}
if(flag == 0)
{
break;
}
cout << "Collection #"<<ID<<":"<<endl;
if(sum%2 == 1)
{
cout << "Can't be divided."<<endl<<endl;
continue;
}
if(sum/2==DP_fun(sum/2))
{
cout << "Can be divided."<<endl<<endl;
}
else
{
cout << "Can't be divided."<<endl<<endl;
}
}
return 0;
}