题解

1 条题解

  • 0
    @ 2023-02-21 23:05:34

     有条件背包/有依赖背包/捆绑背包,同NOIP2006提高组的【金明的预算 】
     二次动归:
      设f(i,j) 表示前 i 种游戏机,花费 j 元钱,能得到的最大收益
      对于第i种游戏机,其选择有:
       1、不买,此时运行于它上面的游戏也不能买,则 f(i,j)=f(i-1,j)

       2、买,此时需要先花去C[i]元买游戏机,然后再考虑运行于其上的游戏,是一个0/1背包问题:
        设d(j) 表示花j元钱去买游戏机i上的游戏,能得到的最大收益
          d(j)= max(d[j],d[j-p[i][k]] + e[i][k])

        于是对于f(i,j):假设花x元用于第i种游戏机及其游戏,的最大收益是d[x-C[i]],则剩下 j-x 用于前面 i-1 款游戏的最大收益f(i-1,j-x),于是有:
        f(i,j) = max{f(i-1,j-x) + d[j-x-C[i]] | C[i]<=x<=j}

      这种算法时间复杂度:O(n*m*m),会超时!

     优化:
       对算法1中选择购买第i种游戏,对于f(i,j)中j元分两部分,j-x用于前面i-1种游戏机,x用于第i中游戏机,于是我们
       设:d[j]表示前i种游戏机花j元钱,在第i种游戏机必买的情况下,的最大收益
        d(j)的初值: d(j)=f(i-1,j-C[i])
        然后: d(j)= max{ d(j),d(j-p[i][k]+e[i][k])
        于是f(i,j)= max(f(i-1,j) , d(j) )
        此时的时间复杂度为:O(n*10*m)

  • 1

信息

ID
1649
难度
(无)
分类
动态规划 | 背包 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
5
上传者