动态规划：最大化问题——职业面试重复选对背包问题

嘿，这个问题其实是经典的无限背包问题的变种——我们要最大化数对的n1值总和（相当于“价值”），同时保证所有选中数对的n2值总和（相当于“占用容量”）不超过给定的K，而且数对可以重复选取。下面给你详细拆解解法：

先把问题的关键要素明确下来：

• 每个数对(n1, n2)：n1是我们要最大化的目标值，n2是该数对消耗的“容量”
• 约束条件：所有选中数对的n2之和 ≤ K
• 可选规则：数对可以重复选取（这是区别于0-1背包的核心点）

动态规划是解决这类最优化问题的标准方案，步骤清晰且效率可控：

1. 定义状态数组 #

我们定义dp[i]表示当可用容量为i时，能获得的最大n1总和。

2. 状态转移方程 #

对于每个容量i（从1到K），遍历列表里的每一个数对(val, cost)（这里val=n1，cost=n2）：
如果当前数对的cost ≤ i（也就是容量足够放下这个数对），那么我们有两种选择：

• 不选这个数对：保持dp[i]的当前值不变
• 选这个数对：此时剩余容量为i-cost，对应的最大价值是dp[i-cost]，加上当前数对的val就是新的可能价值
  我们取这两种选择里的最大值更新dp[i]，公式如下：

dp[i] = max(dp[i], dp[i - cost] + val)

3. 初始化状态 #

• dp[0] = 0：当容量为0时，无法选取任何数对，所以最大n1总和为0
• 其余dp[i]初始化为0（默认所有数对的n1都是非负值，如果有负价值的数对，直接忽略即可，因为选它会拉低总和）

4. 获取结果 #

计算完整个dp数组后，dp[K]就是我们要的答案——容量不超过K时的最大n1总和。如果需要知道具体选了哪些数对，还可以通过回溯dp数组来推导。

这里给你一段可直接运行的代码，方便你理解：

def max_n1_sum(K, pairs):
    # 初始化dp数组，长度为K+1，所有元素初始为0
    dp = [0] * (K + 1)
    
    for current_capacity in range(1, K + 1):
        for n1, n2 in pairs:
            # 只有当前数对的n2不超过当前容量时，才考虑选取
            if n2 <= current_capacity:
                # 计算选当前数对后的总价值，和当前dp值比较取大
                candidate_value = dp[current_capacity - n2] + n1
                if candidate_value > dp[current_capacity]:
                    dp[current_capacity] = candidate_value
    return dp[K]

• 如果存在n2=0且n1>0的数对：此时可以无限选取这个数对，最大n1总和会是无穷大，需要提前判断这种情况
• 如果数对的n1为负数：直接跳过这类数对，因为选它们只会降低总价值

内容的提问来源于stack exchange，提问作者Lloyd Perera