一个选举问题的递归实现

Question

假设有n个州，第i个州有e[i]个选举人票，有p[i]人口，当赢得p[i]的超过一半人口的投票，即获得了e[i]张选举人票，i<n

例如，i为5，e[5]为3，p[5]为17
即当你拿到了17/2+1=9个人的投票，你就获得了3张选举人票
当你拿到了，比如270张选举人票，你就获得了选举胜利，当选总统

问题:
获得哪些州的选票，可以在当选总统的条件限制下，使p[i]之和最小，要求递归实现

定义州

import java.util.Objects;
public class State {
    String name; // The name of the state
 int electoralVotes; // How many electors it has
 int popularVotes; // The number of people in that state who voted
 public State(String name, int electoralVotes, int popularVotes) {
        this.name = name;
 this.electoralVotes = electoralVotes;
 this.popularVotes = popularVotes;
 }
    @Override
 public String toString() {
        return "State{" +
                "name='" + name + ''' +
                ", electoralVotes=" + electoralVotes +
                ", popularVotes=" + popularVotes +
                "}n";
 }
    @Override
 public boolean equals(Object o) {
        if (this == o) return true;
 if (o == null || getClass() != o.getClass()) return false;
 State state = (State) o;
 return electoralVotes == state.electoralVotes &&
                popularVotes == state.popularVotes &&
                Objects.equals(name, state.name);
 }
}

定义MinInfo

import java.util.ArrayList;
public class MinInfo {
    int popularVotesNeeded; // How many popular votes you'd need.
 ArrayList<State> statesUsed; // Which states you'd carry in the course of doing so.
 public MinInfo(int popularVotesNeeded, ArrayList<State> statesUsed) {
        this.popularVotesNeeded = popularVotesNeeded;
 this.statesUsed = statesUsed;
 }
    @Override
 public String toString() {
        return "MinInfo{" +
                "popularVotesNeeded=" + popularVotesNeeded +
                ", statesUsed=" + statesUsed +
                '}';
 }
}

需要实现

public static MinInfo minPopularVoteToGetAtLeast(int electoralVotes,
                                                     int startIndex,
                                                     ArrayList<State> states){
                                                     //todo 实现这里
}

Answer 1

      const e = [3, 6, 4, 10];
      const p = [20, 34, 24, 70];

      const sum = e.reduce((a, i) => a + i, 0);
      const mid = Math.floor(sum / 2);
      const book = new Map();
      const stack = [];
      let min = Infinity;
      let result;

      function dfs(index, ticket = 0, total = 0) {
        if (index >= e.length) {
          if (ticket > mid && total < min) {
            min = total;
            result = stack.slice();
          }

          return;
        }

        for (let i = index; i < e.length; i++) {
          stack.push(i);
          dfs(i + 1, ticket + e[i], total + p[i]);
          stack.pop();
        }
      }

      dfs(0);
      console.log(min, result);