V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
letianqiu
V2EX  ›  程序员

帮忙看一下我 DP 的解法是不是有问题

  •  
  •   letianqiu · 2018-05-15 15:12:40 +08:00 · 1649 次点击
    这是一个创建于 2145 天前的主题,其中的信息可能已经有所发展或是发生改变。

    d.png 2.png

    根据第一问,需要先按照 deposit 降序排列,然后我的想法就是对于每个 ride,只有玩和不玩两种,所以 naive 的递归

    def __solve(cost, deposit, amount, begin, end):
        if begin == end:
            return 1 if amount >= cost[begin] + deposit[begin] else 0
        else:
            result = __solve(cost, deposit, amount, begin + 1, end)
            if amount >= cost[begin] + deposit[begin]:
                result = max(result, 1 + __solve(cost, deposit, amount - cost[begin], begin + 1, end))
            return result
    

    以此为基础的 DP

    def max_ride(cost, deposit, amount):
        n = len(cost)
        opt = [[0 for _ in range(amount + 1)] for _ in range(n + 1)]
        for i in range(n-1, -1, -1):
            for j in range(1, amount + 1):
                opt[i][j] = opt[i+1][j]
                if j > cost[i] + deposit[i]:
                    opt[i][j] = max(opt[i][j], 1 + opt[i+1][j-cost[i]])
        return opt
    

    第四问就没有想到怎么实现 O(n^2)。初步只是发现如果 T 比所有的押金和费用和都大的话,所有项目都能玩。所以 T 大于一个值之后是没必要计算的

    6 条回复    2018-05-16 12:46:39 +08:00
    geelaw
        1
    geelaw  
       2018-05-15 16:18:47 +08:00   ❤️ 1
    状态 (a, b) 表示前 a 个项目玩了 b 个。令 f(a, b) = 开始需要持有的钱的最小值

    要在前 a 个项目玩 b 个,你可以选择玩第 a 个或者不玩第 a 个

    f(a, b) = min { f(a - 1, b), max { f(a - 1, b - 1), D[a] } + C[a] }

    最后寻找 argmax(m) { f(n, m) <= T }
    letianqiu
        2
    letianqiu  
    OP
       2018-05-15 19:56:12 +08:00
    @geelaw 初始化的时候 f(a, b)是不是应该设为-1,开始之前并不知道最少要花多少钱。另外就是想请问一下你是如何思考得出保存的状态应该是最少需要花多少钱的。现在看来这题和 UVA 10154 的乌龟塔类似,都是需要排序之后保存最少达成 k 需要的 resource,而不是保存最大的 k。另外就是哪些情况下,DP 之前需要对原始的数据排序。
    geelaw
        3
    geelaw  
       2018-05-16 01:37:35 +08:00 via iPhone
    @letianqiu

    只需要知道 f(a,0)=0, f(a,a+1)=+infty 然后按照顺序填表即可。

    因为题目要求 n^2 的算法,所以状态数最多 n^2,要用到钱数限制很容易想到,这个题做多了就会了

    这个 n^2 的算法不需要排序,“排序”是没有普遍定义的(很难说“对数据排序”是一个 universally applicable 的操作),根据解决问题的不同有不同的处理。
    geelaw
        4
    geelaw  
       2018-05-16 01:38:50 +08:00 via iPhone
    另,如果这是你的作业题(或者任何需要你书写报告或代码上交的),你应该给予我 acknowledgement
    letianqiu
        5
    letianqiu  
    OP
       2018-05-16 09:51:01 +08:00
    @geelaw 我又想了一下,不知道是不是我的理解有误,感觉状态方程有问题。“开始需要持有的钱的最小值”这个是不是表示如果前 a 个项目玩 b 个(a>=b),最少需要多少钱。按这样理解,当玩第 a 个的时候,a-1 个项目玩了 b-1 个以后,剩下的钱至少要大于等于 cost[a]+deposit[b],才能玩 a。问题是并不知道 f(a-1, b-1)最后剩余多少钱,也许剩余的钱已经大于等于 deposit[a] + cost[a]了。比如 cost=[1, 1], deposit=[10, 1]的情况。同样有可能发生剩余的钱不够 deposit[a],但是 f(a-1, b-1) > deposit[a]。比如 cost=[3, 1], deposit=[2, 3]
    geelaw
        6
    geelaw  
       2018-05-16 12:46:39 +08:00 via iPhone
    @letianqiu 是那个意思。懒得思考,那就先把项目按照押金递减排序吧,这样转移方程就是正确的了。考虑玩第 a 项且前 a-1 项玩了 b-1 项的情况,这样玩:先玩第 a 项,退完押金再玩前 a-1 项里的 b-1 项。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2744 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 12:46 · PVG 20:46 · LAX 05:46 · JFK 08:46
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.