5 solutions

  • 0
    @ 2024-10-26 11:11:00 
    n,T = map(int,input().split())
data = list(map(int,input().split()))
def dfs1(x,sum):
    if x ==x1+1:
        v1.append(sum)
        return 
    dfs1(x+1,sum+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])
    dfs2(x+1,sum)

x1 = n//2
x2 = (n+1)//2
a = data[:x1]
b = data[x1:]
v1,v2 = [],[]
dfs1(1,0)
dfs2(1,0)
v1.sort()
v2.sort()

max_res = 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
    max_res = max(max_res,v1[i]+v2[x])
print(max_res)
    • 0
      @ 2024-10-18 17:11:52

      题面解释:

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

      题解

      该题可以使用状态压缩动态规划（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((2n/2)log⁡(2n/2))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);
    }
}
      • 0
        @ 2024-10-15 12:11:30 
        #include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void calculate(const vector<int>& work, int start, int end, vector<int>& res, int value, int t) {
    if (start > end || value >= t) {
        return ;
    }

    int temp = value + work[start];
    
    if (temp <= t) {
        res.push_back(temp);
    }

    calculate(work, start+1, end, res, temp, t);
    calculate(work, start+1, end, res, value, t);

}

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

    vector<int> cost_1;
    vector<int> cost_2;
    int mid = n/2;

    calculate(work, 0, mid, cost_1, 0, t);
    calculate(work, mid+1, n-1, cost_2, 0, t);

    sort(cost_1.begin(), cost_1.end());
    sort(cost_2.begin(), cost_2.end());

    int res = 0;

    for (int c_1: cost_1) {
        if (c_1 == t) {
            res = c_1;
            break;
        } else if (c_1 < t) {
            int c_2 = t - c_1;
            auto c2 = upper_bound(cost_2.begin(), cost_2.end(), c_2);
            if (c2 != cost_2.begin()) {
                --c2;
                
                res = max(res, c_1 + *c2);

            }
        }
    }

    cout << res << endl;


}
        • 0
          @ 2024-10-12 11:48:30

          简单粗暴，先把大于T的给去掉，然后是看总体sum是否小于等于T，最后是进行dfs，并伴随着剪枝。当ans1+workT.get(i)>timeT，可以只进行dfs(ans1,i+1)。

          import java.util.*;
class Main{
       static long ans = 0L;
       static int timeT;
       static  ArrayList<Integer> workT;
       static Set<Integer> qu;
    public static void main(String[] args) {
        ans = 0L;
        int minD = Integer.MAX_VALUE;
        long sum = 0L;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        timeT = sc.nextInt();
        sc.nextLine();
        String[] work = sc.nextLine().split(" ");
        workT = new ArrayList<>();
        for (int i = 0; i < work.length; i++) {
            int temp = Integer.parseInt(work[i]);
            minD = Math.min(minD, temp);
            if (temp < timeT) {
                workT.add(temp);
               
                sum += temp;
            } else if (temp == timeT) {
                System.out.println(temp);
                return;
            }
        }
        sc.close();
        if (workT.isEmpty()) {
            System.out.println(ans);
        } else {
            //有比他小的
            if (sum <= timeT) {
                //且总体时间较少
                System.out.println(sum);
                return;
            }
            n = workT.size();
            workT.sort(Integer::compareTo);
            qu = new HashSet<>(workT);
            if (qu.size() == 1) {
                for (int i = 0; i < n; i++) {
                    ans += workT.get(i);
                    if (ans > timeT) {
                        ans -= workT.get(i);
                        System.out.println(ans);
                        return;
                    } else if (ans == timeT) {
                        System.out.println(ans);
                        return;
                    }
                }
            }
            //总体时间较多，考虑是否恰好有==timeT
            long ans1=0L;
            int i=0;
            dfs(ans1,i);
            System.out.println(ans);
        }
    }
    private static void dfs(long ans1,int i){
        if(i>=workT.size()||ans>=timeT){
            return;
        }
        ans=Math.max(ans1,ans);
        dfs(ans1,i+1);
        ans1+= workT.get(i);
        if(ans1>timeT){
            return;
        }
        ans=Math.max(ans1,ans);
       if(ans1==timeT||i==workT.size()-1){
           return;
       }
        dfs(ans1,i+1);
    }
    }
          • 0
            @ 2024-9-25 20:28:11

            该题可以使用状态压缩动态规划（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)))，这样就能高效地解决问题。 这样做的好处是大幅降低了复杂度，同时利用二分查找加速了查找过程，使得计算更为高效。

            代码如下

            cpp

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

int n, t;
int a[25], b[25];
int x1, x2;
vector<int> v1, v2; // 使用 vector 动态管理数组
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();
        x--; // 找到不超过 w 的最大值
        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);
    }
}
            • 1

            2024.9.25-秋招-第3题-评估最大工作量

            Information

            ID
            125
            Time
            2000ms
            Memory
            256MiB
            Difficulty
            6
            Tags
            # Submissions
            769
            Accepted
            81
            Uploaded By
            1. About
            2. Contact Us
            3. Privacy
            4. Terms of Service
            5. Copyright Complaint
            6. Language
            7. Legacy mode
            8. Theme
            2. 湘ICP备2023007293号
            3. Worker 0, 26ms
            4. Powered by Hydro v4.14.1 Community