亚麻OA，minimal cost of buying servers

Amazon sells servers to clients, each with an associated cost and efficiency. Given two lists:
        •        cost[i] represents the cost of the i-th server.
        

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

e the efficiency target k. If it’s impossible to reach k, return -1.


没想出来，谁来解答一下

01背包变形问题
from functools import lru_cache                                                                                                                                                                                                                                    

def min_cost_to_reach_efficiency(cost, efficiency, k):
    n = len(cost)
   
    # Memoized DFS function
    @lru_cache(None)
    def dfs(index, curr_efficiency):
        # Base Case: If we reach required efficiency, return 0 cost
        if curr_efficiency <= 0:
            return 0
        # Base Case: If no servers left, return inf (impossible case)
        if index < 0:
            return float('inf')
        
        # Option 1: Skip current server
        skip = dfs(index - 1, curr_efficiency)
        
        # Option 2: Take current server (add its cost & efficiency)
        take = cost[index] + dfs(index - 1, curr_efficiency - efficiency[index])
        
        # Return the minimum cost of both choices
        return min(skip, take)
   
    result = dfs(n - 1, k)
    return result if result != float('inf') else -1

# Example usage
cost = [3, 10, 5]
efficiency = [5, 20, 10]
k = 25
print(min_cost_to_reach_efficiency(cost, efficiency, k))  # Output: 13

标准的背包问题。。dp可以秒

把问题直接丢到ChatGPT里面，就得到解题思路了，lz试试看

有数据范围吗?

vincent_great 发表于 2025-3-19 23:07
标准的背包问题。。dp可以秒

遇到了一样的题目
我用了背包的思路，一个nested for loop，结果给了memory和time的错误。
换句话说，我这个算法还是不够快。
你觉得该怎么改呢？

匿名用户 发表于 2025-3-30 12:26
遇到了一样的题目
我用了背包的思路，一个nested for loop，结果给了memory和time的错误。
换句话说， ...

应该跟下面类似：
https://github.com/youngyangyang ... 83%8C%E5%8C%85-2.md

这题可能greedy取巧吗