题目描述

FlexEth 技术是一种时分复用的网络技术，能够将物理带宽按照时隙进行分配，任务是根据给定的客户业务带宽需求，在总带宽范围内分配尽可能多的时隙，最大限度地减少未分配的带宽。

约束条件：

• 1G 的子时隙只能分配在 5G 主时隙下，不可跨时隙。
• 如果客户的带宽需求大于等于 5G，则分配的带宽必须是 5G 的整数倍。
• 每个时隙只能被一个客户占用。

输入：

• 第一行：一个整数 N，表示客户数量。
• 第二行：N 个整数，表示每个客户的带宽需求。
• 第三行：一个整数 B，表示总带宽。

输出：

输出能够分配的最大带宽和，若没有成功分配任何带宽，则输出 0。

解题思路

1. 问题拆解： 这道题主要是带宽分配问题。通过时隙的分配，我们可以尽量为每个客户分配带宽，最大化带宽的利用率。

2. 核心思想：

   • 我们可以利用动态规划的思想来解决这个问题。具体来说，我们的目标是对于每个带宽需求，找到一种合理的分配方式，使得未分配的带宽和最小。
   • 由于每个时隙只能被一个客户占用，我们可以遍历所有可能的子集进行分配。

3. 细节处理：

   • 需要注意的是，带宽的分配要遵循一定的规则：1G 的子时隙不能跨 5G 时隙，5G 的需求必须是 5G 的整数倍。
   • 利用 dp 数组记录每种剩余带宽时，能够分配的最大带宽值。

4. 状态表示：

   • dp[k] 表示剩余带宽为 k 时，成功分配的最大带宽。我们从 0 开始，逐步考虑每个客户的带宽需求，并更新 dp 数组。

5. 子集遍历：

   • 我们用一个整数 bt 来遍历所有可能的子集，这样我们就可以尝试不同的分配方式。

6. 优先队列：

   • 使用优先队列 q2 来管理剩余的带宽，用来处理客户的带宽分配情况。

Python 版本

import heapq

def main():
    N = int(input())  # 客户业务数量
    L = list(map(int, input().split()))  # 客户带宽需求列表
    B = int(input())  # 总带宽

    # dp数组初始化为-1，表示当前状态不可达
    dp = [-1] * 4004

    # 遍历所有可能的子集
    for bt in range(1, 1 << N):
        rs = 0  # 记录当前子集的分配带宽
        q1 = B // 5  # B每个部分最多允许5
        q2 = []  # 用来保存剩余的带宽
        kx = 0  # 记录不能处理的物品（带宽）

        # 遍历每个客户，判断该客户是否在当前子集
        for i in range(N):
            x = L[i]
            if (bt >> i) & 1:  # 判断物品i是否在当前子集
                if x >= 5:
                    if (x - 1) // 5 + 1 <= q1:
                        q1 -= (x - 1) // 5 + 1
                        rs += ((x - 1) // 5 + 1) * 5
                    else:
                        kx += x
                else:
                    if q2 and q2[0] >= x:  # 优先队列非空且当前最大带宽能容纳此客户
                        y = heapq.heappop(q2)
                        if y - x > 0:
                            heapq.heappush(q2, y - x)
                        rs += x
                    elif q1 > 0:
                        if 5 - x > 0:
                            heapq.heappush(q2, 5 - x)
                        q1 -= 1
                        rs += x
                    else:
                        kx += x
            else:
                kx += x  # 当前客户不在当前子集中，放到剩余部分

        # 更新dp数组，记录该状态下的最大分配带宽
        dp[kx] = max(dp[kx], rs)

    # 输出结果
    for i in range(4004):
        if dp[i] != -1:
            print(dp[i])
            return

    print(0)

if __name__ == "__main__":
    main()

C++

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

int main() {
    int N, B;
    cin >> N;
    vector<int> L(N);
    
    // 读入L数组
    for (int i = 0; i < N; i++) {
        cin >> L[i];
    }
    
    cin >> B;
    
    // dp数组初始化为-1
    vector<int> dp(4004, -1);
    
    // 遍历所有可能的子集
    for (int bt = 1; bt < (1LL << N); bt++) {
        int rs = 0;   // 记录当前子集的结果
        int q1 = B / 5; // B每个部分最多允许5
        priority_queue<int> q2; // 用来保存剩余的物品
        int kx = 0;    // 记录不能处理的物品

        // 遍历每个物品，判断该物品是否在当前子集中
        for (int i = 0; i < N; i++) {
            int x = L[i];
            if ((bt >> i) & 1) {  // 判断物品i是否在当前子集
                if (x >= 5) {
                    if ((x - 1) / 5 + 1 <= q1) {
                        q1 -= (x - 1) / 5 + 1;
                        rs += ((x - 1) / 5 + 1) * 5;
                    } else {
                        kx += x;
                    }
                } else {
                    if (!q2.empty() && q2.top() >= x) {
                        int y = q2.top();
                        q2.pop();
                        if (y - x > 0) q2.push(y - x);
                        rs += x;
                    } else if (q1) {
                        if (5 - x > 0) q2.push(5 - x);
                        q1--;
                        rs += x;
                    } else {
                        kx += x;
                    }
                }
            } else {
                kx += x;  // 如果不在当前子集，就放到不能处理的物品中
            }
        }
        
        dp[kx] = max(dp[kx], rs);  // 更新dp数组
    }
    
    // 输出结果
    for (int i = 0; i < 4004; i++) {
        if (dp[i] != -1) {
            cout << dp[i] << endl;
            return 0;
        }
    }

    return 0;
}

Java 版本

import java.util.*;

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

        // 输入处理
        int N = scanner.nextInt();  // 客户业务数量
        int[] L = new int[N];
        for (int i = 0; i < N; i++) {
            L[i] = scanner.nextInt();  // 客户带宽需求列表
        }
        int B = scanner.nextInt();  // 总带宽

        // dp数组初始化为-1，表示当前状态不可达
        int[] dp = new int[4004];
        Arrays.fill(dp, -1);

        // 遍历所有可能的子集
        for (int bt = 1; bt < (1 << N); bt++) {
            int rs = 0;   // 记录当前子集的结果
            int q1 = B / 5; // B每个部分最多允许5
            PriorityQueue<Integer> q2 = new PriorityQueue<>(Collections.reverseOrder()); // 用来保存剩余的物品
            int kx = 0;    // 记录不能处理的物品

            // 遍历每个物品，判断该物品是否在当前子集中
            for (int i = 0; i < N; i++) {
                int x = L[i];
                if ((bt >> i &1) == 1) {  // 判断物品i是否在当前子集
                    if (x >= 5) {
                        if ((x - 1) / 5 + 1 <= q1) {
                            q1 -= (x - 1) / 5 + 1;
                            rs += ((x - 1) / 5 + 1) * 5;
                        } else {
                            kx += x;
                        }
                    } else {
                        if (!q2.isEmpty() && q2.peek() >= x) {
                            int y = q2.poll();
                            if (y - x > 0) q2.offer(y - x);
                            rs += x;
                        } else if (q1 > 0) {
                            if (5 - x > 0) q2.offer(5 - x);
                            q1--;
                            rs += x;
                        } else {
                            kx += x;
                        }
                    }
                } else {
                    kx += x;  // 如果不在当前子集，就放到不能处理的物品中
                }
            }

            dp[kx] = Math.max(dp[kx], rs);  // 更新dp数组
        }

        // 输出结果
        for (int i = 0; i < 4004; i++) {
            if (dp[i] != -1) {
                System.out.println(dp[i]);
                return;
            }
        }

        System.out.println(0);
    }
}

题目内容

问题背景

灵活以太$(FlexEth)$技术是一种时分复用的网络技术，该技术通过将物理带宽按照时间进行分片，每个时间片对应一定的接口带宽，每个客户占用一定数量的时间片，实现客户带宽的灵活分配。时间片在标准上称为时隙，支持$5G$和$1G$两种时隙粒度，我们称$5G$为主时隙，$1G$为子时隙，客户业务可分配的带宽是时隙粒度带宽的整数倍。比如我们可以将$50GE$的物理带宽按照$5G$时隙粒度分成$10$个时隙，这些时隙可以分配给多个客户使用，每个客户按照业务带宽需求可以分配多个时隙。

限制一:$1G$子时隙粒度不能跨$5G$分配。

举例$1$:客户业务带宽需求为$2G$，分配"$0[0,1]$“或者"$0[1,4]$”都是合法的,分配"$0[0]$,$1[0]$”则是非法的。

说明:我们使用$x0,x1[y0,y1,...]$这种方式来表达时隙位置信息,$x$表示主时隙编号(从$0$开始)，$y$表示子时隙编号($0$~$4$)。

$x1[y1,y2]$表示$x1$主时隙下的$y1$和$y2$两个子时隙，占用的带宽为$2G$。

限制二:如果客户需求的带宽大于等于$5G$，则只能分配$5G$的整数倍带

举例$2$:客户业务带宽需求为$6G$，分配"$0,1$"或者"$1,9$"都是合法的，分配"$0,1[0]$"则是非法的。

限制三:同一个时隙只能被一个客户业务占用。

编程要求

请实现一种时隙分配算法，为给定的客户业务带宽需求分配时隙，使得未成功分配时隙的客户业务带宽之和最小。

输入描述

输入格式:分三行输入

第一行:客户业务数量$N$，取值范围:$1<=N<=20$.

第二行:客户业务带宽列表$L$，数量和业务数一致，业务带宽取值范围: $0 <L[i]<=B$。

第三行:端口带宽$B$，取值范围$50、100、200$。

说明:带宽单位都是$Gbps$。

输出描述

输出成功分配时隙的客户业务占用的时隙带宽之和，如果没有成功分配时隙的客户，则输出$0$。

名词解释:这里的时隙带宽指的是时隙占用的带宽。

样例1

输入

9
1 3 6 10 30 21 1 2 2
100

输出

84 

说明

输出$84$表示这$9$个客户业务占用的时隙带宽之和。其中，各个客户业务的可能的时隙分配如下: $client[0]=0[0]$

$client[1]=0[1,2,3]$

$client[2]=1,2$

$client[3]=3,4$

$client[4]=5,6,7,8,9,10$

$client[5]=11,12,13,14,15$

$client[6]=16[0]$

$client[7]=16[1,2]$

$client[8]=16[3,4]$

样例2

输入

9
1 3 6 10 30 21 1 2 2
50

输出

49

说明

按照如下分配方案，可以计算得到分配的时隙带宽之和为$49$: $client[0]=0[0]$

$client[1]=0[1,2,3]$

$client[2]=failed$

$client[3]=1,2$

$client[4]=4,5,6,7 8,9$

$client[5]=failed$

$client[6]=3[0]$

$client[7]=3[1,2]$

$client[8]=3[3,4]$