有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。 下标为 i 处的奶酪被吃掉的得分为： 如果第一只老鼠吃掉，则得分为 reward1[i] 。 如果第二只老鼠吃掉，则得分为 reward2[i] 。 给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个非负整数 k 。 请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大 得分为多少。 示例 1： 输入：reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2 输出：15 解释：这个例子中，第一只老鼠吃掉第 2 和 3 块奶酪（下标从 0 开始），第二只老鼠吃掉第 0 和 1 块奶酪。 总得分为 4 + 4 + 3 + 4 = 15 。 15 是最高得分。

这是一道经典的动态规划问题，可以使用状态压缩和记忆化搜索来解决。具体思路如下：

1. 定义状态：用一个整数 state 表示当前已经选的奶酪集合，第 i 位表示第 i 块奶酪是否已经被选（0 表示未选，1 表示已选）。用一个整数 k 表示还需要选的奶酪数量。

2. 定义状态转移方程：设 f[state][k] 表示当前状态为 state，还需要选 k 块奶酪时的最大得分，那么状态转移方程为：

f[state][k] = max{f[state'][k-1] + sum(reward1[i] for i in unselected1) + sum(reward2[i] for i in unselected2)},

其中 state' 是 state 的一个子集（即去掉若干位的结果），unselected1 和 unselected2 分别表示第一只老鼠和第二只老鼠未选择的奶酪集合。

3. 边界条件：当 k=0 时，f[state][k] 为 0。

4. 最终答案：f[(1<<n)-1][k] 表示最终状态为所有奶酪都已经被选，还需要选 k 块奶酪时的最大得分。

时间复杂度为 O(3^n * n)，空间复杂度为 O(2^n * n)。

相关问题

有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。 下标为 i 处的奶酪被吃掉的得分为： 如果第一只老鼠吃掉，则得分为 reward1[i] 。 如果第二只老鼠吃掉，则得分为 reward2[i] 。 给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个非负整数 k 。 请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大 得分为多少。

这是一道经典的动态规划问题，可以使用背包问题的思路进行求解。定义一个二维数组 dp，其中 dp[i][j] 表示在前 i 块奶酪中，第一只老鼠吃 j 块奶酪时获得的最大得分。则状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + reward1[i], dp[i-1][j-k] + reward2[i]), k = 1,2,...,j

其中 dp[i-1][j] 表示第 i 块奶酪不被吃掉，dp[i-1][j-1] + reward1[i] 表示第 i 块奶酪被第一只老鼠吃掉，dp[i-1][j-k] + reward2[i] 表示第 i 块奶酪被第二只老鼠吃掉，其中 k 为第一只老鼠吃掉的奶酪块数。

最终的结果即为 dp[n][k]。

以下是参考代码：

def maxCheese(reward1, reward2, k):
    n = len(reward1)
    dp = [[0] * (k+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, k+1):
            dp[i][j] = dp[i-1][j]
            if j == 1:
                dp[i][j] = max(dp[i][j], dp[i-1][j-1] + reward1[i-1])
            elif j > 1:
                for l in range(1, j+1):
                    dp[i][j] = max(dp[i][j], dp[i-1][j-l] + reward2[i-1])
            dp[i][j] += reward1[i-1]
    return dp[n][k]

某地老鼠成灾，现悬赏抓老鼠，每抓到一只奖励10元，于是开始跟老鼠斗智斗勇：每天在墙角可选择以下三个操作：放置一个带有一块奶酪的捕鼠夹(t)，或者放置一块奶酪(c)，或者什么也不放(x)。捕鼠夹可重复利

用，但每次只能抓住一只老鼠。假设老鼠数量无限，你会选择怎样的策略来最大化收益？

我的策略是：每天放置一个带有一块奶酪的捕鼠夹。因为放置一块奶酪只能吸引老鼠，但不能保证一定能抓住老鼠，而放置捕鼠夹可以同时吸引老鼠并且有一定的抓住概率，可以最大化收益。同时，每天放置一个捕鼠夹可以保证每天都有机会抓住老鼠，最大化抓老鼠的数量和收益。