题目描述

某设备有 A 和 B 两个通道用于发射信号。每个通道的发射功率由 License 控制，License 可以叠加使用但不能拆分。用户现有 N 个不同功率的 License，希望将这些 License 分配到 A 和 B 两个通道，使得两个通道的总发射功率相同且尽可能大。如果无法实现相同功率的分配，则输出 0。

思路:动态规划

本问题可以转化为经典的分割等和子集问题。目标是将 N 个 License 分成两个子集，使得两个子集的和相等且尽可能大。如果无法实现，则输出 0。

可以使用动态规划（DP）的方法来解决。具体步骤如下：

1.初始化一个字典 dp，用于记录当前可能的功率差值及对应的最大总功率。初始状态为 {0: 0}，表示两个通道的功率差为 0，总功率为 0。$dp_i$代表目前A和B的差值为i，此时最大的总功率。

2.遍历每个 License 的功率 v，对于每一个当前的差值 k(sum_A-sum_B)，尝试将 v 分配给 A 或 B： 分配给 A：新的差值为 k + v，对应的总功率为 sum_A + v。

分配给 B：新的差值为 k - v，对应的总功率保持为 sum_A。 可以得到dp方程为

$next_{dp}[k+v] = max(next_{dp}[k+v], dp[k]+v)$

$next_{dp}[k-v] = max(next_{dp}[k-v], dp[k]+v)$

3.更新 dp 字典，确保对于每一个差值 k，记录下能够达到该差值的最大 sum_A。

4.最终，查找 dp 中差值为 0 的键值对，对应的 sum_A 即为两个通道可以达到的相同最大功率。如果不存在，则输出 0。

时间复杂度

枚举每一个功率(n)，状态一共有(2* n * n)，所以等同于$O(n^3)$

算法步骤

1.处理输入包括 License数量和每一个的功率

2.定义字典或map

3.进行动态规划，求出差值为0的最大功率

4.输出答案

python

def main():
    # 读取输入
    n = int(input())
    a = list(map(int, input().split()))
    
    dp = {0: 0}  # 初始化字典，键为差值，值为对应的最大总功率

    # 遍历每个功率值
    for v in a:
        next_dp = dp.copy()  # 复制当前状态
        for k, value in dp.items():
            # 更新差值为 k + v 的最大总功率
            if (k + v) in next_dp:
                next_dp[k + v] = max(next_dp[k + v], dp[k] + v)
            else:
                next_dp[k + v] = dp[k] + v
            
            # 更新差值为 k - v 的最大总功率
            if (k - v) in next_dp:
                next_dp[k - v] = max(next_dp[k - v], dp[k])
            else:
                next_dp[k - v] = dp[k]
        dp = next_dp  # 更新 dp 为新的状态

    # 输出差值为0时的最大总功率
    print(dp.get(0, 0))

if __name__ == "__main__":
    main()

c++

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

int main() {
    // 读取输入
    int n;
    cin >> n;
    vector<int> a(n);
    for(int &v : a) cin >> v;

    unordered_map<int, int> dp; // 差值: 通道 A 的总功率
    dp[0] = 0; // 初始化，差值为0时，通道 A 的总功率为0

    // 遍历每个 License 的功率
    for(auto v : a){
        unordered_map<int, int> next_dp = dp; // 复制当前状态
        for(auto &[k, sum_A] : dp){
            // 分配给通道 A
            int new_k_A = k + v;
            int new_sum_A_A = sum_A + v;
            if(next_dp.find(new_k_A) != next_dp.end()){
                next_dp[new_k_A] = max(next_dp[new_k_A], new_sum_A_A);
            }
            else{
                next_dp[new_k_A] = new_sum_A_A;
            }

            // 分配给通道 B
            int new_k_B = k - v;
            if(next_dp.find(new_k_B) != next_dp.end()){
                next_dp[new_k_B] = max(next_dp[new_k_B], sum_A);
            }
            else{
                next_dp[new_k_B] = sum_A;
            }
        }
        dp = next_dp; // 更新 dp 为新的状态
    }

    // 输出差值为0时的最大总功率
    if(dp.find(0) != dp.end()){
        cout << dp[0] << endl;
    }
    else{
        cout << 0 << endl;
    }

    return 0;
}

java

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        // 读取输入
        int n = sc.nextInt();
        int[] a = new int[n];
        for(int i=0; i<n; i++) a[i] = sc.nextInt();
        
        Map<Integer, Integer> dp = new HashMap<>(); // 差值: 通道 A 的总功率
        dp.put(0, 0); // 初始化，差值为0时，通道 A 的总功率为0

        // 遍历每个 License 的功率
        for(int v : a){
            Map<Integer, Integer> next_dp = new HashMap<>(dp); // 复制当前状态
            for(Map.Entry<Integer, Integer> entry : dp.entrySet()){
                int k = entry.getKey();
                int sum_A = entry.getValue();
                
                // 分配给通道 A
                int new_k_A = k + v;
                int new_sum_A_A = sum_A + v;
                if(next_dp.containsKey(new_k_A)){
                    next_dp.put(new_k_A, Math.max(next_dp.get(new_k_A), new_sum_A_A));
                }
                else{
                    next_dp.put(new_k_A, new_sum_A_A);
                }

                // 分配给通道 B
                int new_k_B = k - v;
                if(next_dp.containsKey(new_k_B)){
                    next_dp.put(new_k_B, Math.max(next_dp.get(new_k_B), sum_A));
                }
                else{
                    next_dp.put(new_k_B, sum_A);
                }
            }
            dp = next_dp; // 更新 dp 为新的状态
        }

        // 输出差值为0时的最大总功率
        if(dp.containsKey(0)){
            System.out.println(dp.get(0));
        }
        else{
            System.out.println(0);
        }
    }
}

Javascript

function main(){
    const fs = require('fs');
    const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split(/\s+/);
    let idx = 0;
    
    // 读取输入
    const n = parseInt(input[idx++]);
    const a = [];
    for(let i=0; i<n; i++) a.push(parseInt(input[idx++]));
    
    let dp = new Map(); // 差值: 通道 A 的总功率
    dp.set(0, 0); // 初始化，差值为0时，通道 A 的总功率为0

    // 遍历每个 License 的功率
    for(let v of a){
        let next_dp = new Map(dp); // 复制当前状态
        for(let [k, sum_A] of dp.entries()){
            // 分配给通道 A
            let new_k_A = k + v;
            let new_sum_A_A = sum_A + v;
            if(next_dp.has(new_k_A)){
                next_dp.set(new_k_A, Math.max(next_dp.get(new_k_A), new_sum_A_A));
            }
            else{
                next_dp.set(new_k_A, new_sum_A_A);
            }

            // 分配给通道 B
            let new_k_B = k - v;
            if(next_dp.has(new_k_B)){
                next_dp.set(new_k_B, Math.max(next_dp.get(new_k_B), sum_A));
            }
            else{
                next_dp.set(new_k_B, sum_A);
            }
        }
        dp = next_dp; // 更新 dp 为新的状态
    }

    // 输出差值为0时的最大总功率
    if(dp.has(0)){
        console.log(dp.get(0));
    }
    else{
        console.log(0);
    }
}

main();

题目内容

某设备工作时有 $A、B$ 两个通道向外发射信号，每个通道发射信号的功率大小可单独由 $License$ 控制， $License$ 可叠加使用但不能拆分，如将功率为 $2W$ 和 $3W$ 的 $License$ 加载到设备控制 $A$ 通道发射功率，则 $A$ 通道可以 $5W$ 的功率发射信号。用户现有 $N$ 个功率大小不同的 $License$ ，希望使设备的两个通道能够以最大并且相同的功率发射信号。

输入描述

第一行是用户现有 $License$ 数量 $num$ ，值的范围 $[0,50]$

第二行是 $num$ 个整数的数组，数组元素的值表示 $License$ 中功率大小;数组元素值的范围 $[0,50]$

输出描述

每个通道最大可能发射功率，如果无法分配则通道发射功率为 $0$

样例1

输入

5
2 4 6 8 10

输出

14

说明

$6 + 8= 14，4 +10 =14$，每个通道最大发射功率为 $14$

样例2

输入

3
1 2 4

输出

0

说明

现有 $License$ 无法实现合并分配到两个通道，使两个通道的功率相同。