Easy Max

题目

已知有一些点,以及各个点之间的边权值(无向边).现在要将这些点分成两个集合,并且要求两个集合之间点的权值和最大 比如有三个点编号为1,2,3 其中12之间权值为50,23之间权值为40,13之间权值为30. 那么分成(1,3)和(2)两个集合,他们之间权值和为40+50=90为最大 (点的编号从1开始)

示例

解法

package com.company;

import java.util.Scanner;

public class OJ149 {
    // https://oj.rnd.huawei.com/discuss/problems/discussions/533f0073-25be-4f90-a5dc-39d931e62872?navName=python%20%E9%80%92%E5%BD%92%E6%90%9C%E7%B4%A2%20900ms
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] matrix = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }

        int result = DFS(1, 0, 1, n, matrix);
        System.out.println(result);
    }

    private static int DFS(int currentNode, int currentSum, int select, int numOfNodes, int[][] matrix) {
        if(currentNode == numOfNodes) {
            return currentSum;
        }

        int selectSum = currentSum, notSelectSum = currentSum;
        for (int i = 0; i < currentNode; i++) {
            if(getBit(select, i)==1) {
                notSelectSum += matrix[i][currentNode];
            }else{
                selectSum += matrix[i][currentNode];
            }
        }

        int sum1 = DFS(currentNode + 1, selectSum, setBit(select, currentNode), numOfNodes, matrix);
        int sum2 = DFS(currentNode + 1, notSelectSum, resetBit(select, currentNode), numOfNodes, matrix);

        return Math.max(sum1, sum2);
    }

    private static int getBit(int select, int i) {
        return (select >> i) % 2;
    }

    private static int setBit(int select, int i) {
        return select | (1<<i);
    }

    private static int resetBit(int select, int i) {
        return select & (~(1<<i));
    }
}