跳至主要內容

【DP】2023B-第 k 小的和

【DP】2023B-第 k 小的和

题目描述与示例

本题练习地址：https://www.algomooc.com/problem/P3410

题目描述

从n个数中选若干（至少1）个数求和，求所有方案中第k小的和（和相同但取法不同的视为不同方案）。

对于所有数据，1`` ``<=`` ``k`` ``<`` ``2^n， n个正整数每个都不超过10^9。

输入描述

第一行输入2个正整数n, k。

第二行输入这n个正整数。

输出描述

输出第k小的和。

示例一

输入

5 12
1 2 3 5 8

输出

8

说明

前12小的和分别为: 1 2 3 3 4 5 5 6 6 7 8 8

示例二

输入

3 3
1 3 4

输出

4

说明

有7种组合

1`、`3`、`4`、`1 3`、`1 4`、`3 4`、`1 3 4`，其和分别为：`1 3 4 4 5 7 8`，第`3`小的和为`4

解题思路

本题属于路径无关、求方法数的01背包问题。

代码

解法一：背包DP

Python

1维dp哈希表

# 题目：2023B-第k小的和
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：背包DP-1维dp哈希表
# 代码看不懂的地方，请直接在群上提问


from collections import defaultdict


# 输入n和k
n, k = map(int, input().split())
# 输入n个数
nums = list(map(int, input().split()))

# 构建dp哈希表，dp[i]表示获得总和i一共有多少种方法数
# key为某个和的具体值，value为获得该和的方法数
dp = defaultdict(int)
# 要令组合的和为0，只有1种方法，即选择空集，不选择任何数字
dp[0] = 1


# 遍历nums中的所有数字num
for num in nums:
    # 顺序遍历当前dp哈希表中，已经存在的总和以及获得该总和的方法数，
    # 分别用pre_sum, path_num表示
    for pre_sum, path_num in list(dp.items()):
        # 假如从某个总和pre_sum出发，加上当前所选取的数字num
        # 计算得到的新的总和用cur_sum表示
        cur_sum = pre_sum + num
        # 计算得到cur_sum的方法数应该增加path_num种
        dp[cur_sum] += path_num


# 进行完上述dp过程之后，需要对dp哈希表按照总和的大小进行排序
# 在其中挑选出前k小的总和
lst = list(sorted(dp.items())[1:])
# cnt变量用于统计已经获得了cnt种总和
cnt = 0

# 注意：以下过程的时间复杂度为O(M)，其中M = len(dp)
# 该过程也可以利用前缀和+二分查找的方式来进行优化，
# 但由于整道题目的时间复杂度瓶颈在于dp过程，为O(NM)
# 这里使用二分查找进行优化的效果并不会很明显，故略去不表

# 遍历对dp哈希表排序后得到的数组lst
# path_sum和path_num分别为组合总和，以及获得该总和的方案数
for path_sum, path_num in lst:
    # 如果cnt加上path_num后大于等于k，
    # 说明当前path_sum恰好是第k小的总和
    if cnt + path_num >= k:
        # 输出path_sum，同时退出循环
        print(path_sum)
        break
    # 如果cnt + path_num仍然小于k
    # 说明还没到达第k小的数，更新cnt
    cnt += path_num

1维dp数组

# 题目：2023B-第k小的和
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：背包DP-1维dp数组
# 代码看不懂的地方，请直接在群上提问


# 输入n和k
n, k = map(int, input().split())
# 输入n个数
nums = list(map(int, input().split()))
# 计算n个数字的总和，用于确定dp数组的长度
max_sum = sum(nums)

# 构建长度为 sum(nums) + 1 的1维dp数组，dp[i]表示获得总和i一共有多少种方法数
dp = [0] * (max_sum + 1)
# 要令组合的和为0，只有1种方法，即选择空集，不选择任何数字
dp[0] = 1

# 遍历nums中的所有数字num，即先遍历物品
for num in nums:
    # 01背包，故逆序遍历背包
    # 即逆序遍历当前dp数组中，已经存在的总和以及获得该总和的方法数，
    # 分别用pre_sum, path_num表示
    for pre_sum in range(max_sum-num, -1, -1):
        path_num = dp[pre_sum]
        # 假如从某个总和pre_sum出发，加上当前所选取的数字num
        # 计算得到的新的总和用cur_sum表示
        cur_sum = pre_sum + num
        # 计算得到cur_sum的方法数应该增加path_num种
        dp[cur_sum] += path_num

# 注意：以下过程的时间复杂度为O(M)，其中M = len(dp)
# 该过程也可以利用前缀和+二分查找的方式来进行优化，
# 但由于整道题目的时间复杂度瓶颈在于dp过程，为O(NM)
# 这里使用二分查找进行优化的效果并不会很明显，故略去不表

# cnt变量用于统计已经获得了cnt种总和
cnt = 0

# 遍历对dp数组，注意此处在计算方法数时，要去除0，从1开始计算
# path_sum和path_num分别为组合总和，以及获得该总和的方案数
for path_sum, path_num in enumerate(dp[1:], 1):
    # 如果cnt加上path_num后大于等于k，
    # 说明当前path_sum恰好是第k小的总和
    if cnt + path_num >= k:
        # 输出path_sum，同时退出循环
        print(path_sum)
        break
    # 如果cnt + path_num仍然小于k
    # 说明还没到达第k小的数，更新cnt
    cnt += path_num

2维dp数组

# 题目：2023B-第k小的和
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：背包DP-2维dp数组
# 代码看不懂的地方，请直接在群上提问


# 输入n和k
n, k = map(int, input().split())
# 输入n个数
nums = list(map(int, input().split()))
# 计算n个数字的总和，用于确定dp数组的长度
max_sum = sum(nums)
# 往nums的最前面填充一个0
nums = [0] + nums

# 构建大小为 (n+1) * (max_sum+1) 的2维dp数组
# dp[i][cur_sum]表示在考虑了数字i的条件下
# 获得总和cur_sum一共有多少种方法数
dp = [[0] * (max_sum + 1) for _ in range(n+1)]
# 要令组合的和为0，只有1种方法，即选择空集，不选择任何数字
dp[0][0] = 1

# 遍历nums中的所有数字num，即先遍历物品
for i, num in enumerate(nums[1:], 1):
    # 01背包，在考虑dp[i]的时候，需要遍历dp[i-1]数组中，
    # 已经存在的总和以及获得该总和的方法数
    # 分别用pre_sum, path_num表示
    # 由于是2维dp，这里用正序或逆序均不影响
    for pre_sum in range(max_sum-num, -1, -1):
    # 首先将dp[i-1]种的所有值均复制给dp[i]
        path_num = dp[i-1][pre_sum]
        dp[i][pre_sum] = path_num
    # 然后考虑加上num的情况
    for pre_sum in range(max_sum-num, -1, -1):
        path_num = dp[i-1][pre_sum]
        # 假如从某个总和pre_sum出发，加上当前所选取的数字num
        # 计算得到的新的总和用cur_sum表示
        cur_sum = pre_sum + num
        # 在考虑了i的情况下，计算得到cur_sum的方法数，dp[i][cur_sum]即应该增加path_num种
        dp[i][cur_sum] += path_num


# 注意：以下过程的时间复杂度为O(M)，其中M = len(dp)
# 该过程也可以利用前缀和+二分查找的方式来进行优化，
# 但由于整道题目的时间复杂度瓶颈在于dp过程，为O(NM)
# 这里使用二分查找进行优化的效果并不会很明显，故略去不表

# cnt变量用于统计已经获得了cnt种总和
cnt = 0

# 遍历dp[-1]数组，注意此处在计算方法数时，要去除0，从1开始计算
# path_sum和path_num分别为组合总和，以及获得该总和的方案数
for path_sum, path_num in enumerate(dp[-1][1:], 1):
    # 如果cnt加上path_num后大于等于k，
    # 说明当前path_sum恰好是第k小的总和
    if cnt + path_num >= k:
        # 输出path_sum，同时退出循环
        print(path_sum)
        break
    # 如果cnt + path_num仍然小于k
    # 说明还没到达第k小的数，更新cnt
    cnt += path_num

Java

1维dp哈希表

1维dp数组

import java.util.*;

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

        // 输入n和k
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        // 输入n个数
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        // 计算n个数字的总和，用于确定dp数组的长度
        int max_sum = Arrays.stream(nums).sum();

        // 构建长度为 max_sum + 1 的一维dp数组，dp[i]表示获得总和i一共有多少种方法数
        int[] dp = new int[max_sum + 1];
        // 要令组合的和为0，只有1种方法，即选择空集，不选择任何数字
        dp[0] = 1;

        // 遍历nums中的所有数字num，即先遍历物品
        for (int num : nums) {
            // 01背包，故逆序遍历背包
            // 即逆序遍历当前dp数组中，已经存在的总和以及获得该总和的方法数，
            // 分别用pre_sum, path_num表示
            for (int pre_sum = max_sum - num; pre_sum >= 0; pre_sum--) {
                int path_num = dp[pre_sum];
                // 假如从某个总和pre_sum出发，加上当前所选取的数字num
                // 计算得到的新的总和用cur_sum表示
                int cur_sum = pre_sum + num;
                // 计算得到cur_sum的方法数应该增加path_num种
                dp[cur_sum] += path_num;
            }
        }

        // 注意：以下过程的时间复杂度为O(M)，其中M = dp.length
        // 该过程也可以利用前缀和+二分查找的方式来进行优化，
        // 但由于整道题目的时间复杂度瓶颈在于dp过程，为O(NM)
        // 这里使用二分查找进行优化的效果并不会很明显，故略去不表

        int cnt = 0; // cnt变量用于统计已经获得了cnt种总和

        // 遍历对dp数组，注意此处在计算方法数时，要去除0，从1开始计算
        // path_sum和path_num分别为组合总和，以及获得该总和的方案数
        for (int path_sum = 1; path_sum < dp.length; path_sum++) {
            int path_num = dp[path_sum];
            // 如果cnt加上path_num后大于等于k，
            // 说明当前path_sum恰好是第k小的总和
            if (cnt + path_num >= k) {
                // 输出path_sum，同时退出循环
                System.out.println(path_sum);
                break;
            }
            // 如果cnt + path_num仍然小于k
            // 说明还没到达第k小的数，更新cnt
            cnt += path_num;
        }
    }
}

2维dp数组

C++

1维dp哈希表

1维dp数组

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

int main() {
    int n, k;
    cin >> n >> k;

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

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

    vector<int> dp(max_sum + 1, 0);
    dp[0] = 1;

    for (int num : nums) {
        for (int pre_sum = max_sum - num; pre_sum >= 0; pre_sum--) {
            int path_num = dp[pre_sum];
            int cur_sum = pre_sum + num;
            dp[cur_sum] += path_num;
        }
    }

    int cnt = 0;
    for (int path_sum = 1; path_sum < dp.size(); path_sum++) {
        int path_num = dp[path_sum];
        if (cnt + path_num >= k) {
            cout << path_sum << endl;
            break;
        }
        cnt += path_num;
    }

    return 0;
}

2维dp数组

时空复杂度

时间复杂度：O(``NM``)。需要遍历N个不同的数字，每个数字都要考虑M种前置情况。其中M = len(dp)。

空间复杂度：O(``M``)。dp哈希表/1维数组所占空间。如果是使用二维dp数组，则空间复杂度为O(NM)

解法二：回溯

Python

# 题目：2023B-第k小的和
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：回溯
# 代码看不懂的地方，请直接在群上提问


# 输入n和k
n, k = map(int, input().split())
# 输入n个数
nums = list(map(int, input().split()))


# 回溯函数
# nums:     题目给定的数字数组
# ans:      答案数组，储存各种组合总和的值
# path_sum: 当前回溯的路径和
# startIdx: 本次递归中，nums数组中选择的开始索引
def dfs(ans, path_sum, nums, startIdx):
    # 每次递归进入本函数，都找到了一条新路径，将该路径和加入ans中
    ans.append(path_sum)
    # 终止递归条件：startIdx已经到达nums尾部，无需继续进行递归
    if startIdx == len(nums):
        return
    # 横向遍历nums中，从startIdx开始往后的所有索引
    for i in range(startIdx, len(nums)):
        # 获得i对应的数字num
        num = nums[i]
        # 状态更新：将num加入当前路径和path_sum
        path_sum += num
        # 回溯：由于num不能被反复选择，因此选择i+1作为下一次回溯的startIdx
        dfs(ans, path_sum, nums, i+1)
        # 回滚：将num从当前路径和path_sum中减去
        path_sum -= num
        # 注意，以上三行可以用以下一行来表示
        # dfs(ans, path_sum + num, nums, i + 1)


ans = list()
# 调用递归函数的入口，最开始path_sum = 0，startIdx = 0
dfs(ans, 0, nums, 0)
# 获得所有组合总和后，将其进行排序，注意0并不属于nums中任意非空子集的求和
ans.sort()
# 索引k所对应的数，极为第k小的组合总和
print(ans[k])

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        List<Integer> ans = new ArrayList<>();
        dfs(ans, 0, nums, 0);
        ans.sort(null);
        System.out.println(ans.get(k));
    }

    public static void dfs(List<Integer> ans, int pathSum, int[] nums, int startIdx) {
        ans.add(pathSum);
        if (startIdx == nums.length) {
            return;
        }
        for (int i = startIdx; i < nums.length; i++) {
            int num = nums[i];
            pathSum += num;
            dfs(ans, pathSum, nums, i + 1);
            pathSum -= num;
        }
    }
}

C++

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

using namespace std;

void dfs(vector<int>& ans, int pathSum, const vector<int>& nums, int startIdx) {
    ans.push_back(pathSum);
    if (startIdx == nums.size()) {
        return;
    }
    for (int i = startIdx; i < nums.size(); i++) {
        int num = nums[i];
        pathSum += num;
        dfs(ans, pathSum, nums, i + 1);
        pathSum -= num;
    }
}

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

    vector<int> ans;
    dfs(ans, 0, nums, 0);
    sort(ans.begin(), ans.end());
    cout << ans[k] << endl;

    return 0;
}

时空复杂度

时间复杂度：O(2^N)。由二项式定理可知需要计算一共2^N种组合。本题较难进行剪枝。

空间复杂度：O(1)。忽略递归需要调用的编译栈所占空间。

本站内容包括机考真题解析、八股文速记、技术&行为面试指南、真实上岸经验与截图墙。
Copyright © 2025 欧弟算法