• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1837 – Balance

    ACM-POJ EXP 206阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    提示:动态规划,01背包

    初看此题第一个冲动就是穷举。。。。不过再细想肯定行不通= =O(20^20)等着超时吧。。。

    我也是看了前辈的意见才联想到01背包,用动态规划来解

    题目大意

    有一个天平,天平左右两边各有若干个钩子,总共有C个钩子,有G个钩码,求将钩码全部挂到钩子上使天平平衡的方法的总数。

    其中可以把天枰看做一个以x轴0点作为平衡点的横轴

    输入:

    2 4 //C 钩子数 与 G钩码数

    -2 3 //负数:左边的钩子距离天平中央的距离;正数:右边的钩子距离天平中央的距离c[k]

    3 4 5 8 //G个重物的质量w[i]

    解题思路

    dp思路

    每向天平中方一个重物,天平的状态就会改变,而这个状态可以由若干前一状态获得。

    首先定义一个 平衡度j 的概念

    当平衡度j=0时,说明天枰达到平衡,j>0,说明天枰倾向右边(x轴右半轴),j<0则相反

    那么此时可以把平衡度j看做为衡量当前天枰状态的一个值

    因此可以定义一个 状态数组dp[i][j],意为在挂满前i个钩码时,平衡度为j的挂法的数量。

    由于距离c[i]的范围是-15~15,钩码重量的范围是1~25,钩码数量最大是20

    因此最极端的平衡度是所有物体都挂在最远端,因此平衡度最大值为j=15*20*25=7500。原则上就应该有dp[ 1~20 ][-7500 ~ 7500 ]。

    因此为了不让下标出现负数,做一个处理,使使得数组开为 dp[1~20][0~15000],则当j=7500时天枰为平衡状态

    那么每次挂上一个钩码后,对平衡状态的影响因素就是每个钩码的 力臂

    力臂=重量 *臂长 = w[i]*c[k]

    那么若在挂上第i个砝码之前,天枰的平衡度为j

     (换言之把前i-1个钩码全部挂上天枰后,天枰的平衡度为j)

    则挂上第i个钩码后,即把前i个钩码全部挂上天枰后,天枰的平衡度 j=j+ w[i]*c[k]

     其中c[k]为天枰上钩子的位置,代表第i个钩码挂在不同位置会产生不同的平衡度

    不难想到,假设 dp[i-1][j] 的值已知,设dp[i-1][j]=num

      (即已知把前i-1个钩码全部挂上天枰后得到状态j的方法有num次)

     那么dp[i][ j+ w[i]*c[k] ] = dp[i-1][j] = num

    (即以此为前提,在第k个钩子挂上第i个钩码后,得到状态j+ w[i]*c[k]的方法也为num次)

    想到这里,利用递归思想,不难得出 状态方程dp[i][ j+ w[i]*c[k] ]= ∑(dp[i-1][j])

    有些前辈推导方式稍微有点不同,得到的 状态方程为dp[i][j] =∑(dp[i – 1][j – c[i] * w[i]])

    其实两条方程是等价的,这个可以简单验证出来,而且若首先推导到第二条方程,也必须转化为第一条方程,这是为了避免下标出现负数

    结论

    最终转化为01背包问题

    状态方程dp[i][ j+ w[i]*c[k] ]= ∑(dp[i-1][j])

    初始化:dp[0][7500] = 1; //不挂任何重物时天枰平衡,此为一个方法

    复杂度O(C*G*15000) 完全可以接受

    转载请注明:EXP 技术分享博客 » POJ1837 – Balance

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址