0%

创新班总结7.15

今天,我们迎来了夏令营的第一天,而老师,也为我们准备了许多丰富多彩的知识。

引入:现在桌子上有N颗小石子,我们假设每一颗小石子的价值都为1,那么我们现在可已将若干个小石子合并在一起,变成几堆石子。那么,我们应该如何分配,才可以使堆数最少,且可以表示1至N的价值(就是说,任意几堆可以加在一起表示一个价值)。

如图,是N=8的一种情况(其实也是最优):

他不见了。

那么,价值1用堆1表示,价值2用堆2表示,价值3用堆1和堆2表示,依此类推。事实上,堆4只是多余的没有用途。

二进制:细心点我们可以发现,每一堆的个数都是1,2,4,8,16,……,2k-1,r(剩余的)。那么,这一分法就是题目所要求的吗?如何证明呢?

他不见了。

其实,把数字都看成二进制数,就容易多了。对于一颗长度在k位的二进制数,对于每一位来说,不论是0或是1,它都对应这一个2的幂数。如图括号所示。

那么,剩下的那个数r呢?假设前面按二进制分配好后和为S,那么S+1到S+r怎么表示呢?现在,我们已经可以表示1至S的每一个数了,那么,S+1至S+r的每一个数都减去一个r,必然在1至S之中,因此,配合上r这一堆,我们,就可以表示1至S+r的数了。要注意,对于按二进制分配好后,剩下的那个数r不要忘记了,它也算是一堆。

引入2:现在有一个天平,你可以控制k个砝码的重量,使得可以承重1至N的物品,如何分配。

当然,你可以用上面二进制的方法,但还有更好的方法吗?如图是一种称法:

他不见了。

说明天平可以两边同时放砝码。这范围又扩大了。

二进制不行,三进制可以吗?

三进制:当然可以。

他不见了。

首先,我们需要称量1克的物品,需要1克的砝码。

称量2克的物品,目前最多可以称量1克物品,那么我们需要一个砝码重G,使G-1=2,那么G=3,我们需要一个3克的砝码。

称量3克的物品,直接用3克的砝码。

称量4克的物品,用3克加上1克的砝码。

称量5克的砝码,目前最多可以称量4克物品,那么我们需要一个砝码重G,使G-4=5,那么G=9,我们需要一个9克的砝码。

……

那么,我们发现,砝码重量的变化是1,3,9,27,……,3k-1。其实,上面我们如此一条一条地举例归纳,是我们研究问题的一种重要的方法,那就是归纳法。

应用(部分背包问题O(nlog2n)):01背包问题,完全背包问题,在此就不一一详谈了。

【题意】部分背包问题,就是有一个大小为load的背包,有N个物品,每一个物品有对应的体积w,价值v,数量t,们如何取舍,使放入背包的物品价值最高。

【以前思路】我们就在01背包的基础上,加多一层循环,枚举物品的数量,即把1个物品,2个物品,3个物品捆绑起来,达成一个新的物品,但是,缺点显而易见,时间复杂度O(n2)。

【二进制思路】由上可知,二进制的方法可以表示1-N的个数,却堆数最少(石子问题)。那么,我们就不需要把1个物品,2个物品,3个物品捆绑起来,只需把1个物品,2个物品,4个物品捆绑起来,这样,既可以表示一个物品的所有次数,而且,时间爱你复杂度也将到了O(nlog2n)。

注意, 按二进制捆绑好后,剩下的次数r不要忘记了。

【程序】

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.in");
ofstream fout("Pack_part.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];

for (int i=0; i!=n; ++i) {
int P=1;
for (;((P<<1)<t[i]);P<<=1) //P是控制当前捆绑的次数的,因此P每一次都乘以2
for (int j=load; j>=P*w[i]; --j)
F[j]=max(F[j-P*w[i]]+P*v[i],F[j]);//01背包的做法,只是重量,价值要乘上P

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

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

int ans=-100000000;
for (int i=0; i<=load; ++i)
ans=max(ans,F[i]);

fout << ans;
return 0;
}

感想:二进制是以个神奇的东西,在很多方面都可以得到应用,特别是在时间复杂度方面,可以降至log2n,这是非常重要的。

而且,今后的学习可能会更加辛苦,需要我加倍的努力,因此,我应该发奋学习,学好总结,一分耕耘一分收获。

Thank you so much.