二进制思想
- 格式：doc
- 大小：53.50 KB
- 文档页数：4
1.你让工人为你工作7天，回报是一根金条，这个金条平分成相连的7段，每天结束的时候,工人会向你要一段金条。
如果只允许你两次把金条弄断，你如何给你的工人付费？
2.有1000个苹果，将它们放在100个箱子里，怎么放才能让我向你要苹果的时候，你都能整箱整箱的给我,你的给法是否唯一?
这两个题目我想很多人都曾做过，如果你会做第一个题目，那你也应该会做第二个...如果不会,请看文章标题的提示...
下面就个人理解给出这种二进制的思想:
我第一次看到的是第二个题目，一开始，没什么思路，只是一步步的试，比如说，如果要一个苹果，我就必须要有一个箱子里放1个苹果，这是没法改的，如果要两个苹果，我要么是给一个放有2个苹果的箱子，要么是给两个各放有1个苹果的箱子，显然后面那种不行，因为当向我们要三个苹果的时候，我们至少要用掉三个箱子...后来突然想到高中涂高考志愿卡时,遇到的一个有趣的1248码,卡片只给出四个涂色框,第一个表示1第二个表示2,第三个表示4,第四个表示8,如果我们的号码中有个数字是7,我们就将1 2 4都涂上.
很好,由1,2,4,8这几个数字,我们可以看出,它们能组成1-15中的任何一个数字,如果我们就用这种方法,用掉4个箱子,那第五个箱子,我们就必须要放16个苹果,这样一来,可以组成1-31中的任何一个数字,第六个箱子我们得放32个...依此类推,我们放的是1,2,4,8,16,32...惊讶的发现:这组数字的规律是一个以2为比的等比递增数列,自然而然想到二进制化十进制的方法,11111111B=2的7次幂+2的6次幂+2的5次幂+2的4次幂+... 如此一来,如果我们让每个箱子各对应一个具有10bit的二进制的一位,1表示在第n个箱子放2的n次幂个苹果,我们可以算出,0000000000B~1111111111B的表数范围为:0-1023,而且可以看出,每一个在这中间的数
都可以唯一的对应一个二进制数,也就是说针对不同数目的苹果,我们给箱子的时候,只有一种给法,因为只有1000个苹果,所以最后一个箱子我们没有放512个苹果,而是只放了489个,那么
1-488只有唯一的给法,489-1000有两种给法.(更正一下:只有489-511有两种给法...1-488和
512-1000都只有唯一的给法...)
显然,第一个题目也是用到了这种思想,我们可以将金条分成1、2、4三段,不管哪天工人向我们要金条,我们都能给他,比如说:工人第一天没有要金条,第二天要的时候,我们给他2段,第三天他没有要,第四天他要我们给金条,于是我们将那块四段的给他,收回那个2段的...
二进制思想和多重背包问题
二进制思想
问题描述：
假设有1000个苹果，现在要取n个苹果，如何取？正常的做法应该是将苹果一个一个拿出来，直到n个苹果被取出来。
又假设有1000个苹果和10只箱子，如何快速的取出n个苹果呢？可以在每个箱子中放2^i (i<=0<=n)个苹果，也就是1、2、4、8、16、32、64、128、256、489（最后的余数），相当于把十进制的数用二进制来表示，取任意n个苹果时，只要推出几只箱子就可以了。
多重背包问题
问题描述：
有N种物品和一个容量为V的背包。
第i 种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
问题分析：
很容易想到可以把该问题转化成01背包问题来考虑，把每n[i] 中的每个物品都当成一个独立的物品，而这n[i] 个物品能够表示的重量其实用log n[i]个组合后的物品就能表示。
内层循环代码如下：
int k, t;
k = 1;
t = n[i];
while(t > k)
{
for(j=W; j>=c[i]*k; --j)
{
f[j] = max(f[j], f[j-c[i]*k] + w[i]*k);
}
t -= k;
k *= 2;
}
for(j=W; j>=c[i]*t; --j)
{
f[j] = max(f[j], f[j-c[i]*t] + w[i]*t);
}
背包问题是一个经典的动态规划模型，容易描述，容易理解。
背包问题可简单描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
01背包问题的特点是，每种物品仅有一件，可以选择放或不放。
01背包问题描述：
有N件物品和一个容量为V的背包。
第i件物品的重量是c[i]，价值是w[i]。
求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
写出状态转移方程：
f[i][v]=max{f[i-1][v], f[i-1][v-c[i]]+w[i]}
f[i][v]: 前i件物品恰放入一个容量为v的背包可以获得的最大价值
f[i-1][v]: 前i-1件物品……（同上），即不放入第i件物品的情况
f[i-1][v-c[i]]+w[i]: 放入第i件物品的情况，放入后的f[i][v] 应该等于前i-1 件物品在容量为v-c[i] 上的最大价值加上w[i]空间优化：
f[i][v]=max{f[i-1][v], f[i-1][v-c[i]]+w[i]}
观察黑色字体部分，发现二维数组完全可以用一维数组替代：
f[v]=max{f[v], f[v-c[i]]+w[i]}
程序怎么写？循环如何写？
首先考虑如果所有的物品都能放进去，那一定就是最大价值，如果只能放进去i （i<N）件物品，那一定要选择一个最优策略，这个策略的结果是价值最大，而每个i 的最优策略实际上又是基于i-1 的最优策略的。
根据分析写出如下循环for(i=0; i<N; ++i)
for(v=V; v>w[i]; --v) //逆序推能够保证 f[v-c[i]] 保存的是状态是f[i-1][v-c[i]] ，也就是每个物品只被使用了一次；顺序的话f[v-c[i]] 保存的是f[i][v-c[i]] ，每个物品有可能被使用多次，也就是完全背包问题的解法。
f[v]=max(f[v], f[v-c[i]]+w[i])。
