0%

部分背包问题的补充

关于部分背包问题,之前我们已经阐述了O(nlog2n)的算法。但是我们要注意,这是建立在背包不一定需要装满的情况下,若是背包一定需要恰好装满,那么会怎么样呢?两者之间有什么不同呢?

这有着本质上的不同。

部分背包:f[i] 两种要求(不同题目):

重量<=i的最优值

重量==i的最优值

如图(若物品大小,价值均为5):

他不见了。

事实上,对于每一格,存放的是当前容量,可放置的最大价值.若是存放当前容量,恰好放置的最大价值。如图:

他不见了。

假设我们每一个都初始化为-1,充当着哨兵,表示没有存放任何东西(第0位要改为0,因为接下来才可以放东西)。背包DP时,我们i从总容量load-w扫描0(倒着),判断当前的容量是否为-1,不是,那么F[i+w]才可以进行状态转移。

程序如下:

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
#include <fstream>
using namespace std;

ifstream fin("Pack_part_fill-up.in");
ofstream fout("Pack_part_fill-up.out");

#define maxn 1000
#define maxload 10000

int w[maxn],v[maxn],t[maxn],n,load;
int F[maxload];

int main() {
fin >> n >> load;
for (int i=0; i!=n; ++i)
fin >> w[i] >> v[i] >> t[i];//读入

memset(F,-1,sizeof(F));//整个数组清为-1
F[0]=0;//但是第0位要为0
for (int i=0; i!=n; ++i) {
int P=1;
for (;((P<<1)<=t[i]);P<<=1) //二进制捆绑
for (int j=load-P*w[i]; j>=0; --j)//倒着的
if (F[j]!=-1)//当前容量不为-1才行
F[j+P*w[i]]=max(F[j]+P*v[i],F[j+P*w[i]]);

P=t[i]-(P>>1);
if (P==0) continue;

for (int j=load-P*w[i]; j>=0; --j)
if (F[j]!=-1)
F[j+P*w[i]]=max(F[j]+P*v[i],F[j+P*w[i]]);
}

fout << F[load];//最后直接输出F[load],不用找最大了
return 0;
}
Thank you so much.