题面解释:

小塔的团队面临一个大项目，包含$n$个需求，每个需求需要不同的人天工作量。团队的工作量预算为$T$人天，目标是选择一些需求，使得在不超过$T$人天的前提下，所选需求的工作量总和最大。每个需求要么全部完成，要么不做。输入包含两行，第一行是两个整数$n$和$T$，第二行是$n$个整数，表示每个需求的工作量。输出一个整数，表示在预算内可以完成的最大工作量。

题解

该题可以使用状态压缩动态规划（DP）或深度优先搜索（DFS）结合二分查找来解决。由于背包容量可达到 10^9，而物品数量 n 为 40，使用普通的 01 背包算法显然不可行，因为 2^40 的复杂度会爆炸。因此，我们可以将物品分成两个组，每组最多有 20 个物品，这样总的复杂度将减少到 2^20，大约在 100 万级别，仍然可以接受。

具体思路如下：

1.对于每个组，使用状态压缩 DP 或 DFS 计算出所有可能的组合（重量和价值）。$\\$ 2.枚举第一个组的每个组合 x，然后利用二分查找找到第二组中最接近 T - x 的组合 y。$\\$ 3.更新答案为 ans = max(ans, x + y)。$\\$ 整体时间复杂度为 O((2^(n/2)) log(2^(n/2)))，这样就能高效地解决问题。 这样做的好处是大幅降低了复杂度，同时利用二分查找加速了查找过程，使得计算更为高效。

1. 分组与组合生成：

   • 将需求分成两组，分别为a和b。
   • 使用深度优先搜索（DFS）生成每组的所有组合的工作量。

2. 组合搜索：

   • 遍历第一组的每个组合x，然后在第二组中利用二分查找找到不超过T - x的最大组合y。
   • 更新答案为ans = max(ans, x + y)。

3. 效率优化：

   • 通过对第二组的组合数组进行排序，并使用upper_bound进行快速查找，可以显著提高查找效率。

整体时间复杂度为$O((2^{n/2}) \log(2^{n/2}))$，使得计算过程更加高效。

解释

1. 数据输入：程序首先读取需求数量和预算，然后分别读取两组需求的工作量。
2. DFS组合生成：通过递归的方式生成每组需求的所有组合并存储。
3. 组合查找：利用二分查找寻找在预算内的最大组合，最终输出满足条件的最大工作量。

代码如下

cpp

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, t; // n为需求数量，t为工作量预算
int a[25], b[25]; // 分别存储两组需求的工作量
int x1, x2; // x1和x2为两组需求的数量
vector<int> v1, v2; // 用于存储组合的工作量
int cnt1 = 0, cnt2 = 0; // 记录组合数量

// 深度优先搜索（DFS）生成第一组的组合
void dfs1(int x, int sum) {
    if (x == x1 + 1) { // 当所有物品都考虑完毕
        v1.push_back(sum); // 将当前组合的工作量加入结果集
        return;
    }
    dfs1(x + 1, sum + a[x]); // 选择当前物品
    dfs1(x + 1, sum);        // 不选择当前物品
}

// 深度优先搜索（DFS）生成第二组的组合
void dfs2(int x, int sum) {
    if (x == x2 + 1) { // 当所有物品都考虑完毕
        v2.push_back(sum); // 将当前组合的工作量加入结果集
        return;
    }
    dfs2(x + 1, sum + b[x]); // 选择当前物品
    dfs2(x + 1, sum);        // 不选择当前物品
}

signed main() {
    cin >> n >> t; // 输入需求数量和预算
    x1 = n / 2; // 第一组物品数量
    x2 = (n + 1) / 2; // 第二组物品数量

    for (int i = 1; i <= x1; i++) {
        cin >> a[i]; // 输入第一组的工作量
    }
    for (int i = 1; i <= x2; i++) {
        cin >> b[i]; // 输入第二组的工作量
    }

    // 生成两组的所有组合
    dfs1(1, 0);
    dfs2(1, 0);

    // 对组合数组进行排序
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());

    v2.push_back(1e18); // 添加一个极大值以方便查找

    int mx = 0; // 记录最大值
    for (int i = 0; i < v1.size(); i++) {
        if (v1[i] > t) break; // 超过预算限制则停止
        int w = t - v1[i]; // 计算剩余的预算
        int x = upper_bound(v2.begin(), v2.end(), w) - v2.begin(); // 找到不超过 w 的最大值
        x--; // 获取最大值的索引
        mx = max(mx, v1[i] + v2[x]); // 更新最大值
    }

    cout << mx << '\n'; // 输出结果
    return 0;
}

python

def dfs1(x, sum):
    if x == x1 + 1:
        v1.append(sum)
        return
    dfs1(x + 1, sum + a[x - 1])  # 将 a[x] 改为 a[x - 1]
    dfs1(x + 1, sum)

def dfs2(x, sum):
    if x == x2 + 1:
        v2.append(sum)
        return
    dfs2(x + 1, sum + b[x - 1])  # 将 b[x] 改为 b[x - 1]
    dfs2(x + 1, sum)

n, t = map(int, input().split())
arr = list(map(int, input().split()))
x1 = n // 2
x2 = (n + 1) // 2
a = arr[:x1]  # 保持从 0 开始
b = arr[x1:]  # 保持从 0 开始

v1, v2 = [], []
dfs1(1, 0)
dfs2(1, 0)

v1.sort()
v2.sort()
v2.append(float('inf'))

mx = 0
for i in range(len(v1)):
    if v1[i] > t:
        break
    w = t - v1[i]
    x = next((j for j in range(len(v2)) if v2[j] > w), len(v2)) - 1
    mx = max(mx, v1[i] + v2[x])

print(mx)

java

import java.util.*;

public class Main {
    static int n, t;
    static int[] a = new int[25];
    static int[] b = new int[25];
    static int x1, x2;
    static List<Long> v1 = new ArrayList<>();
    static List<Long> v2 = new ArrayList<>();

    static void dfs1(int x, long sum) {
        if (x == x1 + 1) {
            v1.add(sum);
            return;
        }
        dfs1(x + 1, sum + a[x]);
        dfs1(x + 1, sum);
    }

    static void dfs2(int x, long sum) {
        if (x == x2 + 1) {
            v2.add(sum);
            return;
        }
        dfs2(x + 1, sum + b[x]);
        dfs2(x + 1, sum);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        t = sc.nextInt();
        x1 = n / 2;
        x2 = (n + 1) / 2;

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

        dfs1(1, 0);
        dfs2(1, 0);

        Collections.sort(v1);
        Collections.sort(v2);
        v2.add(Long.MAX_VALUE);

        long mx = 0;
        for (long value : v1) {
            if (value > t) {
                break;
            }
            long w = t - value;
            int x = Collections.binarySearch(v2, w);
            if (x < 0) {
                x = -(x + 1) - 1;
            }
            mx = Math.max(mx, value + v2.get(x));
        }

        System.out.println(mx);
    }
}

题目内容

某团队来了一个大项目，该项目已知有$n$个需求，每个需求工作量分别需要$t_1、t_2、t_3.......t_n$人天，由于该项目需求过多，负责人小明决定先给出$T$人天预算完成部分需求。对于单个需求，每个任务要么不做，要么全部完成，必须耗时$ti$人天完成，现在小明想知道$T$人天的预算最多能做多少人天的需求。

输入描述

输入共两行

首行是$2$个整数，以空格隔开，分别是$n$和$T$，$n$代表需求总数，$T$代表工作量评估不超过$T$人天

次行有$n$个整数，以空格隔开，分别是$t_1、t_2、t_3....t_n$，代表每个需求所需工作量，单位是人天

数据范围:$1≤n≤40;1≤ti≤10^9;1≤T≤10^9$

输出描述

一个整数$Ans$，代表$T$人天的预算最多能做$Ans$人天的需求

样例1

输入

5 17
2 3 5 11 7

输出

17

说明

该项目有$5$个需求，工作量评估不超过$17$人天，每个需求工作量分别需要$2$人天、$3$人天、$5$人天、$11$人天、$7$人天;

小明选择需求$1$、需求$2$、需求$3$、需求$5$，所需工作量总和是$2+3+5+7=17$

样例2

输入

6 100
1 2 7 5 8 10

输出

33

说明

该项目有$6$个需求，工作量评估不超过$100$人天，每个需求工作量分别需要$1$人天、$2$人天、$7$人天、$6$人天、$8$人天、$10$人天;

小明选择全部需求，所需工作量总和是$1+2+7+5+8+10=33$

样例3

输入

6 100
101 102 103 104 105 106

输出

0

说明

该项目有$6$个需求，工作量评估不超过$100$人天，每个需求工作量分别需要$101$人天、$102$人天、$103$人天、$104$人天、$105$人天、$106$人天;

小明无论选择哪个需求都超过了$100$人天，所需工作量总和最大是$0$人天