研究 DSA 问题好几天了，但无法解决

Question

在过去一周左右的时间里，我遇到了一个 HackerRank 问题（只能通过私人链接获得），这似乎是一个贪婪算法问题。不幸的是，只有 1 个测试用例可用，因此调试很困难，但我只通过了 3 个测试用例中的 1 个。我创建了一个我认为是正确的解决方案，但结果总是不正确。这是一个具有多重约束的问题，因此这是最令人困惑的一点。我将发布问题、我的伪代码/解决方案和我的代码。如果有人能够和我一起集思广益，那就太好了。我需要第二双眼睛来关注这个问题。

问题：

作为其积极扩张战略的一部分，X 公司正在寻求投资各种创新项目。由于财力和人力资源有限，公司需要谨慎选择承接的项目。这个问题需要一种有效的方法来根据项目的潜在利润、所需资本和人力需求来管理和确定项目的优先级。您的任务是开发一种使用堆（优先级队列）来优化这些决策的算法。

你有n个项目。每个项目都由其潜在利润 (profits[i])、所需资本 (capital[i]) 和人力需求 (manpower[i]) 定义。

X 公司开始时拥有 w 资本和 h 人力单位。完成一个项目会根据项目的利润增加公司的资本，但会根据项目的人力需求减少可用的人力。

您的目标是通过选择最多 k 个项目来最大化 X 公司的最终资本。

您的目标是通过选择最多 k 个项目来最大化 X 公司的最终资本。该解决方案必须使用堆（优先级队列）有效地确定项目的优先级，以确保选择最佳的项目组合。 输入：k=2，w=0，h=5，利润=[3,2,5]，资本=[0,1,1]，人力=[2,3,4]

输出：5

说明：由于你的初始资本为0，所以你只能启动资本值为0的项目，项目索引为0，完成后你将获得利润3，你的资本变成0+3=3，人力变成5-2= 3.资金为 3，人力为 3，您可以启动索引为 1 的项目或索引为 2 的项目。由于您最多可以选择 2 个项目，因此您需要完成索引为 1 的项目才能获得最大资本，因为您只剩下3 人力。因此，输出最终最大化的资本，即3+2=5，人力变为3-3=0

我的方法：

1. 创建一个空列表来存储项目及其信息。遍历它们并将项目添加到列表中
2. 创建一个最大堆（PriorityQueue）来根据利润降序存储项目。
3. 迭代项目。 虽然有可行的项目（资金要求在可用资本范围内的项目），但将它们添加到最大堆中。
4. 如果最大堆不为空，则选择利润最大的项目。 根据所选项目更新可用资金和人力。
5. 重复步骤3和4，直到没有更多可行的项目可用或选择了所需数量的项目。
6. 该方法最终返回的结果是根据指定条件选择项目后的availableCapital。

代码：

public static int maximizeCapital(int numProjects, int initCapital, int initManpower, List<Integer> projectProfits, List<Integer> projectCapitals, List<Integer> projectManpowers) {
        List<int[]> projects = new ArrayList<>();
        for (int i = 0; i < numProjects; i++) {
            projects.add(new int[]{projectProfits.get(i), projectCapitals.get(i), projectManpowers.get(i)});
        }

        // Max heap to store projects based on profit (maximize profit)
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);

        int availableCapital = initCapital;
        int availableManpower = initManpower;

        for (int i = 0; i < numProjects; i++) {
            // Add feasible projects to max heap
            while (!projects.isEmpty() && projects.get(0)[1] <= availableCapital) {
                maxHeap.offer(projects.remove(0));
            }

            // Select the project with maximum profit
            if (!maxHeap.isEmpty()) {
                int[] selectedProject = maxHeap.poll();
                availableCapital += selectedProject[0];  // Update capital
                availableManpower -= selectedProject[2];  // Update manpower
            } else {
                break;  // No more feasible projects
            }
        }

        return availableCapital;
    }

测试用例通过：

输入（标准输入）

2 0 5 3 
3 2 5 
0 1 1 
2 3 4

您的输出（标准输出）

5 

预期输出

5

Answer 1

您的方法似乎足以合理地实现利润最大化，我刚刚看到一个流程，这可能是您使用所选利润的利润更新资本的问题，但简而言之，您应该使用所选项目的资本要求这是更新 -

// Select the project with maximum profit
if (!maxHeap.isEmpty()) {
    int[] selectedProject = maxHeap.poll();
    availableCapital += selectedProject[1];  // Update capital using the capital requirement
    availableManpower -= selectedProject[2];  // Update manpower
} else {
    break;  // No more feasible projects
}

在更新可用资本时，我将

selectedProject[0]

替换为

selectedProject[1]

，以确保所选项目的资本要求，您的代码应该正常工作，但如果失败，请提供更多输入（测试用例）。