作业4

名字：余明叶学号：20111602310026班级：计本（1）班课本112页6在120枚外观相同的硬币中，有一枚是假币，并且知道假币和真币的重量不同，但不知道假币和真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，最坏情况下，能不能只比较5次就检测出这枚硬币？1)把它分成48，48，24（这样分就能把它们用6个为一组，即48里面有8个小组每个小组有6个硬币）。接着随便拿两份到天平上称，有几种情况：第1种：第1次，先从简单的做起，也就是说第一次48：48正好天平平衡，就是说明假硬币在24中。现在我把范围缩小到24个硬币（即4个小组每组6个。）第2次，然后我就从48个硬币中选三个组跟24个硬币中的三个组来称。继续用简单的方法假设天平平衡，（现在只剩6个球啦！就是一个组。）第3次，把6个分成三组每个组两个硬币，随便选两个组称（假设天平平衡，那么就只剩一组即两个硬币）第4次，在两个硬币中选一个和正常的称（假设天平平衡，那么只剩一个硬币啦！）第5次，再把最后一个硬币跟正常的称，正常的那边重的话就说明它（假币）比真的轻，反之则重。2）(接住1.的）假设第1次不变，第2次假如是48个硬币中选出来的重{反之则把轻和重换一下}（那么假币一定是比真的要轻。现在只剩24个硬币中三个小组）第3次，随便拿两个小组到天平中称（假设天平平衡，那么假币必定在最后一个小组里面。）第4次，现在把剩下的6个硬币分成三组，每组两个。随便称两组，（假设天平平衡，那么假币一定在剩下的两个里面）第5次，称剩下的两个硬币，轻的就是假币。3）（接住2.的)第1次，第2次，都不变第3次，假设是有一个小组比较重的话（可以把轻的6个硬币像二.中的第4次，第5次。称出结果）上面的轻的和重的是相对的，可以同时调换，不影响结果。4)（接住1.的）现在到最复杂的：第1次，天平不平衡（有一边是比较重的，先记下对后面有用。接着把第一堆的8各小组分成4个小组即每个组12个硬币，第二堆也分成4个小组即每个组12个硬币。把它们编号第一堆{1，2，3，4}第二堆{5，6，7，8}）第2次，把1，2，5和3，4，6放到天平中称，（第1次，中假如是第一堆重。那么假设在第2次，中天平平衡。可以判断假币是比较轻的）第3次，（我从正常的硬币中选3个出来，加上原来的24个硬币一共有27个。我把27个硬币分成3个小组，每组9个）任意选两个组称（假设天平平衡，那么轻的假币在最后的9个硬币里面，然后我把剩下的9个分成3组每个组有3个硬币）第4次，任意选两个组（假设天平平衡，那么轻的假币在最后的3个硬币。第5次，只要随便称两个就可以确定假币在哪里啦！（假设天平平衡，那么剩下的就是假币。如果不平衡那么轻的那个就是假币。）注：轻的和重的可以同时换，就是指关联的。5)（接住4.的）第1次，不变，第2次，天平不平衡（第1次，中假如是第一堆重。如果是1，2，5那边重则假币在1，2里面并且是重的。）第3次，还是借3个硬币方法跟第四步的第3次以后一样，这里就不多说啦！看回第2次（如果1，2，5是轻的。那么假币在5里面并且是轻的。）课本137页3用动态规划法求如下0/1背包问题的最优解：有5个物品，其重量分别为（3,2,1,4,5），物品的价值分别为（25,20,15,40，50），背包容量为6。写出求解过程。解：令V（i,j)表示在前i个（1≤i≤n)个物品中能够装入容量为j(1≤j≤C)的背包中的物品的最大值。动态规划函数：V(i,0)=V(0,j)=0（6.11）V(i,j)=V（i-1,j)jiwmax{V(i-1,j),V(i-1,j-iw)+iv}j≥iw（6.12)函数：ix=0V(i,j)=V(i-1,j)1,j=j-iwV(i,j)V(i-1,j)(6.13)根据动态规划函数，用一个（n+1)x(C+1)的二维表V，V[i][j]表示把前物品装入容量为的背包中获得的最大价值。根据式（6.11）把表的第0行和第0列初始化为0，然后一行一行地计算V[i][j]，如下图所示；0123456X000000001w=31v=2510002525252502w=22v=20200202525454503w=13v=153015203540456014w=44v=404015203540556005w=55v=50501520354055651从图中可以看到，装入背包的物品的最大价值是65，根据式（6.13),装入背包的物品为X={0,0,1,0,1}。