一、考察频率以及难度

考察频率：⭐⭐⭐⭐⭐

笔试题难度：⭐⭐⭐

算法难度：⭐⭐⭐

此类题型一般是属于中等题。

二、学习技巧

需要掌握好背包模型的本质，能够快速识别到背包类型的题目。

并且此类题型的模板性比较强，熟练掌握模板可以快速地秒杀。

三、应用场景

一般使用的场景：多个物品做出一些选择，达到最优的某个目的。其中，一般对于物品的选择有一定的限制，比如数量、重量等，这个一般就是背包问题的背包容量。

四、算法讲解

背包模型的核心在于：n个物品做一些选择，使得最终 值最大/值最小/数量最多等。解题思路就是：挨个物品考虑，每个物品有两种选择：选和不选。

背包最常见的两类模型：

1. 01背包：f(i, j) → f(i - 1, j), f(i - 1, j - v[i])。f(i, j)只依赖于f(i - 1, j)和f(i - 1, j - v[i])。因此base case是f(0, j)，一般dp数组定义为dp[n + 1][w + 1]，这样dp[0][j]的含义就是没有物品的时候的最优解，这样做是为了便于初始化。

2. 完全背包：f(i, j) → f(i - 1, j), f(i, j - v[i])。f(i, j)只依赖于f(i - 1, j)和f(i, j - v[i])。可以看出，“完全背包”和“01背包”的区别只在于选的时候依赖不同，因为物品是不限制数量的，因此就算选了第i个物品，也可以继续考虑第i个物品。

代码模板如下

int n, C; //n个物品， C表示背包容量
int[] v,  w; //v[i]表示第i个物品的价格/体积    w[i]表示第i个物品的价值
int[][] dp = new int[n + 1][C + 1]; //容器规模
dp[0][j]; //初始化
for (int i = 1 ; i <= n ; i++) {
    for (int j = 0 ; j <= C ; j++) {
        if (j >= v[i - 1]) dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i-1]] + w[i - 1]);
        else dp[i][j] = dp[i - 1][j];
    }
}
return dp[n][C];

int n, C; //n个物品， C表示背包容量
int[] v,  w; //v[i]表示第i个物品的价格/体积    w[i]表示第i个物品的价值
int[][] dp = new int[n + 1][C + 1]; //容器规模
dp[0][j]; //初始化
for (int i = 1 ; i <= n ; i++) {
    for (int j = 0 ; j <= C ; j++) {
        if (j >= v[i - 1]) dp[i][j] = max(dp[i-1][j], dp[i][j-v[i-1]] + w[i - 1]);
        else dp[i][j] = dp[i - 1][j];
    }
}
return dp[n][C];

滚动数组：不难发现“01背包”和“完全背包”的依赖关系都取决于(i -1, j - a)和(i, j - a)。因此可以用一个一维数组dp[j]来表示这个过程，也就是初始化的时候dp[j]表示的是i == 0的值，然后依次将dp[j]改为 1, 2, 3, ...., n的值。

01背包的依赖如下：

对于任意节点（黄色）(i, j)都依赖于上一行的两个值也就是i - 1这一行的值。因此可以复用一个一维数组来替代二维数组。注意：01背包使用一维数组表示一定要从一维数组从大到小来进行填表，否则会导致依赖的值被覆盖而导致出错！

int n, C; //n个物品， C表示背包容量
int[] v,  w; //v[i]表示第i个物品的价格/体积    w[i]表示第i个物品的价值
int[] dp = new int[C + 1]; //容器规模
dp[j]; //初始化
for (int i = 1 ; i <= n ; i++) {
    for (int j = C ; j >=  v[i - 1] ; j--) {
        dp[j] = max(dp[j], dp[j-v[i-1]] + w[i - 1]);
    }
}
return dp[C];

完全背包的依赖如下：

对于任意节点（黄色）(i, j)都依赖于(i - 1,j) 和(i, j - v[i]) 。因此依然可以复用一个一维数组来替代二维数组。注意：完全背包使用一维数组表示一定要从一维数组从小到大来进行填表，否则会出现依赖的值还没算而依赖错值！

int n, C; //n个物品， C表示背包容量
int[] v,  w; //v[i]表示第i个物品的价格/体积    w[i]表示第i个物品的价值
int[] dp = new int[C + 1]; //容器规模
dp[j]; //初始化
for (int i = 1 ; i <= n ; i++) {
    for (int j = v[i - 1] ; j <= c ; j++) {
        dp[j] = max(dp[j], dp[j-v[i-1]] + w[i - 1]);
    }
}
return dp[C];

这一部分在笔试考察的比例非常非常高，因为特别方便进行场景的结合。

五、例题与解析

习题1 神秘海域

https://oj.niumacode.com/problem/P1103

在一个神秘的宝藏岛上，有一群探险家发现了一袋宝石。每颗宝石都有不同的重量，探险家们想要公平地分配这些宝石。为了避免争执，他们希望能将宝石分成两个子集，使得每个子集的总重量相等。你的任务是判断是否能够实现这种分割。

输入:

• 第一行包含一个整数n ，表示数组的长度。

• 第二行包含 n 个正整数，表示数组的元素。

输出:

• 输出一个Yes或No，表示是否可以将数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入

4
1 5 11 5

输出

Yes

解释

数组可以分割成 [1, 5, 5] 和 [11]。

示例 2：

输入

4
1 2 3 5

输出

No

提示：

1 <= nums.length <= 200

1 <= nums[i] <= 100

题目解析

“一个数组是否可以平均分为2份”等价于“能否找到一个子集，使得子集的和为数组总和的一半”。

因此，这就是一个01背包问题。数组中的数字就是物品，总和一半就是背包容量。

因此可以直接条用背包的模板。

1. 状态转移方程式：dp[i][j]表示考虑前i个数字，能否凑出 j。第i个数字可以选也可以不选，也就是dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]

2. 容器规模：i表示数字，范围为[0, n]。j表示背包容量，范围为[0, target]

3. base case：dp[0][j]，含义是考虑第0个数字（也就是没有数字）的时候，能否凑出j，因此只能凑出0，所以dp[0][0] = true，其他的均为false。

4. 填表顺序：从i=1行开始填，一行一行填即可。

代码展示

二维背包

Java Code

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        
        if (totalSum % 2 != 0) {
            System.out.println("No");
        } else {
            int target = totalSum / 2;
            boolean[][] dp = new boolean[n + 1][target + 1];
            dp[0][0] = true;
            
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= target; j++) {
                    if (j >= nums[i - 1]) {
                        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
            
            if (dp[n][target]) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
        
        scanner.close();
    }
}

Python Code

n = int(input())
nums = [int(c) for c in input().split()]

total_sum = sum(nums)
if total_sum % 2 != 0:
    print("No")
else:
    target = total_sum // 2
    n = len(nums)
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    dp[0][0] = True
    for i in range(1, n + 1):
        for j in range(target + 1):
            if j >= nums[i - 1]:
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
            else:
                dp[i][j] = dp[i - 1][j]
    if dp[-1][-1]:
        print("Yes")
    else:
        print("No")

C++ Code

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    int totalSum = 0;
    for (int num : nums) {
        totalSum += num;
    }

    if (totalSum % 2 != 0) {
        cout << "No" << endl;
    } else {
        int target = totalSum / 2;
        vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
        dp[0][0] = true;

        for (int i

习题2 凑硬币

https://oj.niumacode.com/problem/P1104

在一个奇妙的魔法王国里，国王决定举行一场有趣的挑战，来测试居民们的智力和运气。国王准备了许多不同面额的硬币，并设定了一个目标金额。挑战的目标是使用最少数量的硬币凑成这个目标金额。如果不能用任何组合的硬币凑成目标金额，挑战者将会失败。

你的任务是帮助挑战者找到解决方案，计算并返回可以凑成总金额所需的最少硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。

输入:

• 第一行包含一个整数 n ，表示硬币的种类数。

• 第二行包含 n 个正整数，表示不同面额的硬币。

• 第三行包含一个整数 m，表示总金额。

输出:

• 输出一个整数，表示可以凑成总金额所需的最少硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1：

输入

3
1 2 5
11

输出

3

解释

11 = 5 + 5 + 1

示例 2：

输入

1
2
3

输出

-1

 

提示：

1 <= n <= 12

0 <= amount <= 10^4

题目解析

此题是典型的完全背包问题。

1. 状态转移方程式：dp[i][j]考虑前i个硬币，凑出 j 元最少需要的硬币数。dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i])

2. 容器规模：i 的范围是[0, coins.length] j 的范围是 [0, amount]

3. base case：dp[0][j]表示考虑前0个硬币凑出j的最少硬币数，除了dp[0][0] = 0以外，其余的均凑不了，也就是没有硬币的情况下，只能凑出0，其他的金额都凑不了，因此这里用一个比较大的数字表示（因为amount最大是10^4，因此我们用10001表示最大值）

4. 顺序：i = 1 开始填表。

代码展示

二维背包

Java Code

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] coins = new int[n];
        for (int i = 0; i < n; i++) {
            coins[i] = scanner.nextInt();
        }
        int amount = scanner.nextInt();
        scanner.close();
        System.out.println(coinChange(coins, amount));
    }

    public static int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        Arrays.fill(dp[0], 10001);
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= amount; j++) {
                if (j >= coins[i - 1])
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[n][amount] == 10001 ? -1 : dp[n][amount];
    }
}

Python Code

def coinChange(coins, amount):
    n = len(coins)
    dp = [[10001] * (amount + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    for i in range(1, n + 1):
        for j in range(amount + 1):
            if j >= coins[i - 1]:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1)
            else:
                dp[i][j] = dp[i - 1][j]
    return dp[n][amount] if dp[n][amount] != 10001 else -1

if __name__ == "__main__":
    n = int(input())
    coins = list(map(int, input().split()))
    amount = int(input())
    print(coinChange(coins, amount))

C++ Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int coinChange(vector<int>& coins, int amount) {
    int n = coins.size();
    vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 10001));
    dp[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= amount; ++j) {
            if (j >= coins[i - 1]) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n][amount] == 10001 ? -1 : dp[n][amount];
}

int main() {
    int n;
    cin >> n;
    vector<int> coins(n);
    for (int i = 0; i < n; ++i) {
        cin >> coins[i];
    }
    int amount;
    cin >> amount;
    cout << coinChange(coins, amount) << endl;
    return 0;
}

习题3 美食挑战

https://oj.niumacode.com/problem/P1105

给在一个繁忙的城市中，有一家叫做 "Binary Bytes" 的餐厅，这家餐厅的菜单上只有两种类型的菜肴：素食（用“0”表示）和肉食（用“1”表示）。每道菜的名称都是一个二进制字符串。一天，餐厅的老板决定举办一个有趣的挑战，来测试顾客们的智慧和策略。

挑战的目标是从菜单中选择尽可能多的菜肴组成一个子集，使得子集中最多有 m 道素食菜和 n 道肉食菜。你的任务是帮助顾客找到这样的最大子集，并返回该子集的长度。

输入:

• 第一行包含一个整数len ，表示字符串数组的长度。

• 接下来 len 行，每行包含一个二进制字符串。

• 最后一行包含两个整数 n 和 m 。

输出:

• 输出一个整数，表示满足条件的最大子集的长度。

示例 1：

输入

5
10
0001
111001
1
0
5 3

输出

4

解释

最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，
因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入

3
10
0
1
1 1

输出

2

解释

最大的子集是 {"0", "1"} ，所以答案是 2 。

 

提示：

1 <= strs.length <= 600

1 <= strs[i].length <= 100

strs[i] 仅由 '0' 和 '1' 组成

1 <= m, n <= 100

题目解析

此题是裸背包问题，不需要进行转换，不同的是背包的限制有两个维度，一个是0的数量，一个1的数量。

1. 状态转移方程式：dp[i][j][k]表示考虑前i个字符串，有j个0和k个1，可以选取的最大子集是多大。 dp[i][j][k] = max(dp[i-1][j][k] , dp[i-1][j - zeros[i]][k - ones[i]] + 1)，zeros[i]表示第i个字符串有多少个0，ones[i]表示第i个字符串有多少个1。

2. 容器规模：i表示第几个字符串，范围是[0, length]。j表示剩余的0的数量，范围是[0, m]。k表示剩余1的数量，范围是[0, n]

3. base case：dp[0][j][k]考虑第0个字符（没有字符）的时候，可以凑出的最大子集，那就都是0就好了。

4. 填表顺序：i从1开始填到n即可。

代码展示

三维背包

Java Code

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int len = scanner.nextInt();
        String[] strs = new String[len];
        for (int i = 0; i < len; i++) {
            strs[i] = scanner.next();
        }
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        
        System.out.println(findMaxForm(strs, m, n));
        
        scanner.close();
    }

    public static int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[] ones = new int[len];
        int[] zeros = new int[len];
        for (int i = 0; i < len; i++) {
            ones[i] = count(strs[i], '1');
            zeros[i] = count(strs[i], '0');
        }
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];

        for (int i = 1; i <= strs.length; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    if (j - zeros[i - 1] >= 0 && k - ones[i - 1] >= 0)
                        dp[i][j][k] = Math.max(dp[i - 1][j - zeros[i - 1]][k - ones[i - 1]] + 1, dp[i - 1][j][k]);
                    else
                        dp[i][j][k] = dp[i - 1][j][k];
                }
            }
        }
        return dp[strs.length][m][n];
    }

    // 计算字符串str中有多少个target字符
    public static int count(String str, char target) {
        int count = 0;
        for (char c : str.toCharArray()) {
            if (c == target)
                count++;
        }
        return count;
    }
}

Python Code

def count(s, target):
    return s.count(target)

def findMaxForm(strs, m, n):
    len_strs = len(strs)
    ones = [count(s, '1') for s in strs]
    zeros = [count(s, '0') for s in strs]

    dp = [[[0] * (n + 1) for _ in range(m + 1)] for _ in range(len_strs + 1)]

    for i in range(1, len_strs + 1):
        for j in range(m + 1):
            for k in range(n + 1):
                if j - zeros[i - 1] >= 0 and k - ones[i - 1] >= 0:
                    dp[i][j][k] = max(dp[i - 1][j - zeros[i - 1]][k - ones[i - 1]] + 1, dp[i - 1][j][k])
                else:
                    dp[i][j][k] = dp[i - 1][j][k]

    return dp[len_strs][m][n]

if __name__ == "__main__":
    len_strs = int(input())
    strs = [input().strip() for _ in range(len_strs)]
    m, n = map(int, input().split())
    print(findMaxForm(strs, m, n))

C++ Code

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int count(const string& str, char target) {
    int count = 0;
    for (char c : str) {
        if (c == target)
            count++;
    }
    return count;
}

int findMaxForm(vector<string>& strs, int m, int n) {
    int len = strs.size();
    vector<int> ones(len);
    vector<int> zeros(len);
    for (int i = 0; i < len; i++) {
        ones[i] = count(strs[i], '1');
        zeros[i] = count(strs[i], '0');
    }
    vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));

    for (int i = 1; i <= len; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= n; k++) {
                if (j - zeros[i - 1] >= 0 && k - ones[i - 1] >= 0)
                    dp[i][j][k] = max(dp[i - 1][j - zeros[i - 1]][k - ones[i - 1]] + 1, dp[i - 1][j][k]);
                else
                    dp[i][j][k] = dp[i - 1][j][k];
            }
        }
    }
    return dp[len][m][n];
}

int main() {
    int m, n, len;
    cin >> len;
    vector<string> strs(len);
    for (int i = 0; i < len; i++) {
        cin >> strs[i];
    }
    cin >> m >> n;
    cout << findMaxForm(strs, m, n) << endl;
    return 0;
}

习题4 商品购物 【美团】

https://oj.niumacode.com/problem/P1147

题目描述

现在商店里有N个物品，每个物品有原价和折扣价。

小美想要购买商品。小美拥有X元，一共Y张折扣券。

小美需要最大化购买商品的数量，并在所购商品数量尽量多的前提下，尽量减少花费。

你的任务是帮助小美求出最优情况下的商品购买数量和花费的钱数。

输入描述

第一行三个整数，以空格分开，分别表示N,X,Y。

接下来N行，每行两个整数，以空格分开，表示一个的原价和折扣价。

1≤N≤100, 1≤X≤5000, 1≤Y≤50，每个商品原价和折扣价均介于[1,50]之间。

输出描述

一行，两个整数，以空格分开。第一个数字表示最多买几个商品，第二个数字表示在满足商品尽量多的前提下所花费的最少的钱数。

示例1

输入

3 5 1
4 3
3 1
6 5

输出

2 5

思路与代码

动态规划(背包问题)的题目。

定义状态dp[i,j,k]的含义为：考虑前i个物品，剩余金额为j，剩余优惠券为k，可以购买的最大物品数。

状态转移

对于每个商品，有三种可能的选择：

1. 不买这个商品。

2. 按原价买这个商品（如果剩余金额足够）。

3. 使用折扣券按折扣价买这个商品（如果剩余金额和折扣券足够）。

初始化

dp[0][j][k] = 0：在没有商品的情况下，无论剩余多少金额和多少折扣券，最多购买的商品数量都是 0。

CPP

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

int main() {
    int N, X, Y;
    cin >> N >> X >> Y;

    vector<pair<int, int>> goods(N);
    for (int i = 0; i < N; ++i) {
        cin >> goods[i].first >> goods[i].second;
    }

    vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(X + 1, vector<int>(Y + 1, 0)));

    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= X; ++j) {
            for (int k = 0; k <= Y; ++k) {
                dp[i][j][k] = dp[i - 1][j][k];  // 不买当前商品
                if (j >= goods[i - 1].first) {
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - goods[i - 1].first][k] + 1);  // 按原价买
                }
                if (k >= 1 && j >= goods[i - 1].second) {
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - goods[i - 1].second][k - 1] + 1);  // 按折扣价买
                }
            }
        }
    }

    int maxCnt = 0, minFee = INT_MAX;
    for (int j = 0; j <= X; ++j) {
        for (int k = 0; k <= Y; ++k) {
            if (dp[N][j][k] > maxCnt) {
                maxCnt = dp[N][j][k];
                minFee = j;
            } else if (dp[N][j][k] == maxCnt) {
                minFee = min(minFee, j);
            }
        }
    }

    cout << maxCnt << " " << minFee << endl;

    return 0;
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int X = scanner.nextInt();
        int Y = scanner.nextInt();

        int[][] goods = new int[N][2];
        for (int i = 0; i < N; i++) {
            goods[i][0] = scanner.nextInt();
            goods[i][1] = scanner.nextInt();
        }

        int[][][] dp = new int[N + 1][X + 1][Y + 1];

        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= X; j++) {
                for (int k = 0; k <= Y; k++) {
                    dp[i][j][k] = dp[i - 1][j][k]; // 不买当前商品
                    if (j >= goods[i - 1][0]) {
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - goods[i - 1][0]][k] + 1); // 按原价买
                    }
                    if (k >= 1 && j >= goods[i - 1][1]) {
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - goods[i - 1][1]][k - 1] + 1); // 按折扣价买
                    }
                }
            }
        }

        int maxCnt = 0, minFee = Integer.MAX_VALUE;
        for (int j = 0; j <= X; j++) {
            for (int k = 0; k <= Y; k++) {
                if (dp[N][j][k] > maxCnt) {
                    maxCnt = dp[N][j][k];
                    minFee = j;
                } else if (dp[N][j][k] == maxCnt) {
                    minFee = Math.min(minFee, j);
                }
            }
        }

        System.out.println(maxCnt + " " + minFee);
    }
}

Python

N, X, Y = map(int, input().split(" "))
goods = []
for _ in range(N):
    goods.append([int(c) for c in input().split(" ")])

'''dp[i][j][k]: 最大物品数'''

'''i下标 j剩余金额 k剩余优惠券数量'''
dp = [[[0 for _ in range(Y + 1)] for _ in range(X + 1)] for _ in range(N + 1)]

for i in range(1, N+1):
    for j in range(X+1):
        for k in range(Y+1):
            '''可以买、不买、优惠券买'''
            dp[i][j][k] = dp[i-1][j][k]
            if j >= goods[i-1][0]:
                dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-goods[i-1][0]][k] + 1)
            if k >= 1 and j >= goods[i-1][1]:
                dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-goods[i-1][1]][k-1] + 1)

maxCnt, minFee = 0, inf

for j in range(X+1):
    for k in range(Y+1):
        if dp[N][j][k] >maxCnt:
            maxCnt = dp[N][j][k]
            minFee = j
        elif dp[N][j][k] == maxCnt:
            minFee = min(minFee, j)

print(maxCnt,end=" ")
print(minFee)

习题5 糖果盛宴 【美团】

https://oj.niumacode.com/problem/P1148

题目描述：

小美特别爱吃糖果。小美家楼下正好有一个糖果专卖店，每天供应不同种类的糖果。小美预先拿到了糖果专卖店接下来n天的进货计划表，并针对每天的糖果种类标注好了对小美而言的美味值。小美当然想每天都能去买糖果吃，不过由于零花钱限制（小美零花钱并不多！）以及健康考虑，小美决定原则上如果今天吃了，那么明天就不能吃。但小美认为凡事都有例外，所以她给了自己k次机会，在昨天已经吃了糖果的情况下，今天仍然连续吃糖果！简单来说，小美每天只能吃一次糖果，原则上如果昨天吃了糖果那么今天就不能吃，但有最多k次机会打破这一原则。

小美不想浪费每次吃糖果的机会，所以请你帮帮她规划一下她的吃糖果计划，使得她能吃到的糖果美味值最大。

输入描述

第一行两个整数n和k，表示拿到的进货计划表的天数和最多打破原则的次数。

第二行n个整数a1,a2,...,an，其中ai表示接下来第 i 天糖果专卖店的糖果的美味值。

1≤n≤2000,1≤k≤1000,1≤ai≤10000

输出描述

输出一行一个数，表示小美能吃到的糖果美味值之和最大值。

样例输入

7 1
1 2 3 4 5 6 7

样例输出

19

提示

最优的方案是选择选择第2、4、6天吃糖果，并在第7天打破一次原则也吃糖果（因为第6天已经吃过，原则上不能继续吃，需要使用一次打破原则的机会）。

思路与代码

明显的一道动态规划的题目。类似一个变种的背包问题。

每一个糖果都有以下几种选择：

1. 不吃

2. 正常吃，此时不能考虑下一个糖果，只能跳一个。

3. 特权吃，可以考虑下一个糖果。

因此不难得出以下方程：

设f[i][j]表示前i天中最多允许使用j次打破原则机会时，能获得的最大美味值。

初始条件：

f[1][0] = a[1]：在第一天没有打破原则时的美味值就是当天的美味值。

其他的初始条件视情况而定。

状态转移方程：

如果不打破原则：

• f[i][j] = f[i-2][j] + a[i]（今天吃糖果，前天也可以吃糖果）

• f[i][j] = max(f[i-1][j], f[i][j])（今天不吃糖果，沿用昨天的状态）

如果打破原则：

• f[i][j] = f[i-1][j-1] + a[i]（昨天吃了糖果，今天继续吃糖果，用掉一次打破原则的机会）

填充dp表格：

• 对每一天i，对于每一种打破原则的次数j，通过以上的状态转移方程更新f[i][j]。

结果：

• 最终的答案就是f[n][k]，即在前n天内最多允许使用k次打破原则机会时的最大美味值。

Python

import sys
input = sys.stdin.read

def main():
    data = input().split()
    n = int(data[0])
    k = int(data[1])
    a = [0] * (n + 1)
    index = 2
    for i in range(1, n + 1):
        a[i] = int(data[index])
        index += 1

    f = [[0] * (k + 1) for _ in range(n + 1)]

    for i in range(k + 1):
        f[1][i] = a[1]

    for i in range(2, n + 1):
        for j in range(k + 1):
            f[i][j] = max(f[i - 1][j], f[i - 2][j] + a[i])
            if j > 0:
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + a[i])

    print(f[n][k])

if __name__ == "__main__":
    main()

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n + 1];
        int[][] f = new int[n + 1][k + 1];

        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }

        for (int i = 0; i <= k; i++) {
            f[1][i] = a[1];
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                f[i][j] = Math.max(f[i - 1][j], f[i - 2][j] + a[i]);
                if (j > 0) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + a[i]);
                }
            }
        }

        System.out.println(f[n][k]);
        sc.close();
    }
}

C++

#include<iostream>
#include<cstring>

using namespace std;

int n,k;
int a[2010];
int f[2010][1010];

int main() {
  cin >> n >> k;
  for (int i = 1 ; i <= n ; i++) cin >> a[i];
  for (int i = 0 ; i <= k ;i++) f[1][i] = a[1];

  for (int i = 2 ; i <= n ; i++) {
    for (int j = 0 ; j <= k ; j++) {
        f[i][j] = max(f[i-1][j], f[i-2][j] + a[i]);
        if (j > 0) f[i][j] = max(f[i][j], f[i-1][j-1] + a[i]);
    }
  }
  cout << f[n][k] ;
}

习题6 小马的分享日常 【小红书】

https://oj.niumacode.com/problem/P1164

题目描述

小马很喜欢前往小红书分享她的日常生活。已知她生活中有n个事件，分享第i个事件需要她花费ti的时间和hi的精力来编辑文章，并能获得ai的快乐值。

小红想知道，在总花费时间不超过T且总花费精力不超过H的前提下，小马最多可以获得多少快乐值？

输入描述
第一行输入一个正整数n，代表事件的数量。

第二行输入两个正整数T和H，代表时间限制和精力限制。

接下来的n行，每行输入三个正整数ti,hi，ai，代表分享第i个事件需要花费ti的时间、hi的精力，收获ai的快乐值。

1<=n<=50
1<=T,H<=500
1<=ti,hi<=30
1<=ai<=10^9

输出描述

一个整数，代表小马最多的快乐值

样例

输入

2
2 2
1 3 3
3 1 4

输出

0

说明

显然，小马无法分享任何事件

思路与代码

给定 n 个事件，每个事件都有三个属性：

• t[i]: 需要的时间

• h[i]: 需要的精力

• a[i]: 事件的价值

我们需要在时间 T 和精力 H 的限制下，选择一些事件使得总价值最大化。换句话说，我们需要在有限的资源下，选择一些事件来获取最大的总价值。

这是一个多维的01背包问题，其中背包的维度是时间和精力。dp[i][j][k] 表示前 i 个事件中，使用不超过 j 时间和不超过 k 精力时，能获得的最大总价值。

状态转移
选择第 i 个事件：如果我们选择第 i 个事件，所需的时间和精力分别为 t[i] 和 h[i]。这意味着我们在状态 dp[i-1][j-t[i]][k-h[i]] 的基础上增加事件 i 的价值 a[i]，即：dp[i][j][k]=max(dp[i][j][k],dp[i−1][j−t[i]][k−h[i]]+a[i])
前提是 j >= t[i] 和 k >= h[i]，即当前时间和精力足够容纳事件 i。

不选择第 i 个事件：如果我们不选择第 i 个事件，状态保持不变：
dp[i][j][k]=dp[i−1][j][k]
初始化
基准状态：初始化 dp[0][j][k] = 0，表示没有事件时，任何时间和精力下的最大价值都是 0。

当然，这里可以直接套用滚动数组优化的模板。

CPP

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

int main() {
    int n, T, H;
    cin >> n >> T >> H;

    vector<int> t(n + 1), h(n + 1), a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> t[i] >> h[i] >> a[i];
    }

    // dp[j][k] 表示使用不超过 j 时间和不超过 k 精力时能获得的最大总价值
    vector<vector<ll>> dp(T + 1, vector<ll>(H + 1, 0));

    // 遍历每个事件
    for (int i = 1; i <= n; ++i) {
        // 从大到小遍历时间和精力，确保每个事件只被考虑一次
        for (int j = T; j >= t[i]; --j) {
            for (int k = H; k >= h[i]; --k) {
                dp[j][k] = max(dp[j][k], dp[j - t[i]][k - h[i]] + a[i]);
            }
        }
    }

    // 输出最大总价值
    cout << dp[T][H] ;

    return 0;
}

Java

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int T = sc.nextInt();
        int H = sc.nextInt();

        int[] t = new int[n+1];
        int[] h = new int[n+1];
        int[] a = new int[n+1];
        for (int i = 1; i <= n; i++) {
            t[i] = sc.nextInt();
            h[i] = sc.nextInt();
            a[i] = sc.nextInt();
        }

        long[][] dp = new long[T+1][H+1];

        for (int i = 1 ; i <= n ; i++) {
            for (int j = T; j >= t[i]; j--) {
                for (int k = H ; k >= h[i] ; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j-t[i]][k-h[i]] + a[i]);
                }
            }
        }
        System.out.print(dp[T][H]);
    }

}

Python

def main():
    n, T, H = map(int, input().split())
    t = [0] * (n + 1)
    h = [0] * (n + 1)
    a = [0] * (n + 1)
    
    for i in range(1, n + 1):
        t[i], h[i], a[i] = map(int, input().split())

    # dp[j][k] 表示使用不超过 j 时间和不超过 k 精力时能获得的最大总价值
    dp = [[0] * (H + 1) for _ in range(T + 1)]

    # 遍历每个事件
    for i in range(1, n + 1):
        # 从大到小遍历时间和精力，确保每个事件只被考虑一次
        for j in range(T, t[i] - 1, -1):
            for k in range(H, h[i] - 1, -1):
                dp[j][k] = max(dp[j][k], dp[j - t[i]][k - h[i]] + a[i])

    # 输出最大总价值
    print(dp[T][H])

if __name__ == "__main__":
    main()

六、常见陷阱

1. 初始值的设定一定要考虑好状态的含义。

2. 使用滚动数组的时候，要注意填表的顺序不能乱。