K 件物品的最大和

难度: Easy

袋子中装有一些物品，每个物品上都标记着数字 1 、0 或 -1 。

给你四个非负整数 numOnes 、numZeros 、numNegOnes 和 k 。

袋子最初包含：

numOnes 件标记为 1 的物品。
numZeros 件标记为 0 的物品。
numNegOnes 件标记为 -1 的物品。

现计划从这些物品中恰好选出 k 件物品。返回所有可行方案中，物品上所标记数字之和的最大值。

示例 1：

输入：numOnes = 3, numZeros = 2, numNegOnes = 0, k = 2
输出：2
解释：袋子中的物品分别标记为 {1, 1, 1, 0, 0} 。取 2 件标记为 1 的物品，得到的数字之和为 2 。
可以证明 2 是所有可行方案中的最大值。

示例 2：

输入：numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4
输出：3
解释：袋子中的物品分别标记为 {1, 1, 1, 0, 0} 。取 3 件标记为 1 的物品，1 件标记为 0 的物品，得到的数字之和为 3 。
可以证明 3 是所有可行方案中的最大值。

提示：

0 <= numOnes, numZeros, numNegOnes <= 50
0 <= k <= numOnes + numZeros + numNegOnes

Submission

运行时间: 19 ms

内存: 16.0 MB

class Solution:
    def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:
        # 初始化总和为 0
        total_sum = 0
        
        # 尽可能多地选择标记为 1 的物品
        ones_to_take = min(numOnes, k)
        total_sum += ones_to_take
        k -= ones_to_take
        
        # 如果还需要选择物品并且存在标记为 0 的物品，则选择它们
        zeros_to_take = min(numZeros, k)
        k -= zeros_to_take
        
        # 如果还需要选择物品并且存在标记为 -1 的物品，则尽可能少地选择它们
        neg_ones_to_take = min(numNegOnes, k)
        total_sum -= neg_ones_to_take
        
        return total_sum

Explain

题解的核心思路是优先选取对总和贡献最大的物品。首先尽可能多地选择标记为 1 的物品，因为每个这样的物品都能为总和增加 1。当标记为 1 的物品不足以填满 k 时，选择标记为 0 的物品，这些物品不会增加也不会减少总和。如果还需要选择更多物品，最后选择标记为 -1 的物品，尽管这会减少总和。这个策略确保了在给定的物品和限制下，总和达到可能的最大值。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:
        # 初始化总和为 0
        total_sum = 0
        
        # 尽可能多地选择标记为 1 的物品
        ones_to_take = min(numOnes, k)
        total_sum += ones_to_take
        k -= ones_to_take
        
        # 如果还需要选择物品并且存在标记为 0 的物品，则选择它们
        zeros_to_take = min(numZeros, k)
        k -= zeros_to_take
        
        # 如果还需要选择物品并且存在标记为 -1 的物品，则尽可能少地选择它们
        neg_ones_to_take = min(numNegOnes, k)
        total_sum -= neg_ones_to_take
        
        return total_sum

Explore

在题解中，选择标记为0的物品时没有对总和`total_sum`进行更新的原因是，这些物品的标记值为0，即它们对总和的贡献为零。因此，无论选择多少个标记为0的物品，总和都不会改变。这样的处理简化了计算，并确保了算法的效率。

题解中的算法逻辑已经涵盖了这种情况。当`k`大于所有物品的总和时，算法会尽可能多地选择标记为1的物品，然后是标记为0的物品，最后选择标记为-1的物品。如果`k`仍然大于所有可用物品的数量，即使选择完所有物品，`k`还有剩余，算法就会停止选择，因为没有更多的物品可选择。在这种情况下，总和将是通过选择所有标记为1和0的物品以及必要数量的标记为-1的物品得到的最大可能总和。

是的，选择标记为-1的物品会影响到总和达到最大值的目标。在题解中，尽管尽量避免选择标记为-1的物品，但如果`k`非常大，以至于必须选择这些物品来满足`k`的数量要求，这将不可避免地减少总和。因此，在这种情况下，即使策略是为了最大化总和，总和仍可能受到负面影响，因为每选择一个标记为-1的物品，总和就会减少1。

题解中的算法逻辑确实考虑了这些边界情况。算法的设计允许在`numOnes`, `numZeros`, 或`numNegOnes`任何一个或多个为0时仍然正常工作。算法首先尝试选择尽可能多的标记为1的物品，如果不存在（即`numOnes`为0），则移至下一个标记为0的物品。此逻辑同样适用于`numZeros`和`numNegOnes`。因此，无论输入如何，算法都能正确处理不同的边界情况，并尽可能地提供最优的总和结果。