yhz012 发布于五月 18, 2020 发布于五月 18, 2020 (已修改) 艹基础题是缓存命中问题 附加题……曼哈顿距离，边的权重可变，求traveling sales man…… 我觉得这已经不是不保证了吧，完全可以规约到普通的TSP问题，只要令所有商店的物品重量为0即可…… 五月 18, 2020，由yhz012修改
yhz012 发布于五月 18, 2020 发布于五月 18, 2020 11 分钟前, Mr.K 018 说道: 附加题是我真的想在生活中这么优化一下，所以并没有考虑复杂度（ 那这么看，恐怕只能分支限界一下 我觉得这问题本身确实很有意思，而且直球来说其实我最近在做和这边有关的算法 感觉有一些能挣扎的地方，但是我的大脑现在处于罢工状态……
yhz012 发布于五月 18, 2020 发布于五月 18, 2020 (已修改) 11 小时前, Mr.K 018 说道: 我在想，修改题目中的条件，改成不必只有最后才能回家，而是随时可以回家放东西，出来后身上的重量值回到1，这个题是变得简单了还是更复杂了 我直觉是这俩问题难度一样？但是我还没想好怎么构造问题来互相归约 如果一样，那某种意义上我们可以用最小生成树来求bounded approximate solution。 在想如果我允许vertex的weight是负的，但是agent的weight始终是max(1, tempW)，是不是在原点处增加n个负w顶点就可以归约了…… 我需要证明回家一定只会吃掉手上相同的权重的负w顶点……多吃肯定是亏的，主要问题是少吃的情况…… 五月 18, 2020，由yhz012修改
yhz012 发布于五月 20, 2020 发布于五月 20, 2020 于 2020/5/18 于 AM10点05分, Mr.K 018 说道: 没人来看啊……感觉这个题应该没那么难了吧？ 说实话我操作系统没学好，题目里要求最少，我需要对全局优化么，比如假设全局是 123456789 000000000 111111111 222222222 …… 999999999 那么显然我要是使用最后一次使用离现在最远的策略，毫无疑问我的找方块数的次数要增加，但是这个前提是我预先已经知道了第三行我要用1 换句话说，输入的数据我是否应当视作流数据，每次我只读一行，还是我预先先读取所有行（甚至某种程度上搭方块也可以不按照行的顺序）？
yhz012 发布于五月 20, 2020 发布于五月 20, 2020 (已修改) 48 分钟前, Mr.K 018 说道: 这题不就退化成数输入中有多少个不同的数了吗kora 好像是这么回事（装傻 所以总结来说就是我事先是可以读取所有要用方块的，然后按序摆方块就好了对吧 那我最暴力的写法就是开一个m长数组next，初始化为inf，然后倒序遍历整个像素画，更新记录之后在第几个方块使用，接着正序更新最不迫切需要的方块就好了吧 next = [[float('inf')] for i in range(m)] #初始化全inf index = n for block in reversed(blockList): #倒序遍历 index = index - 1 next[block].insert(index, 0) #记录下次使用index hand = np.full(9, np.inf) #初始化手里的方块 handSize = hand.size #记录手里的空间 count = 0 #记录查找次数 for block in blockList: if block not in hand: #不在手里 if handSize > 0: #手里有空间 hand[handSize] = block #拿到手里 count = count + 1 handSize = handSize - 1 else: #没空间 index = argmax(next[hand]) #手里面的方块中，next最大的 hand[index] = block #替换方块 count = count + 1 next[block].pop(0) #拿在手里后，定位下一个方块位置 return count 五月 20, 2020，由yhz012修改 注释 Mr.K 018 40.00节操 正解！
推荐贴