假设有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 实现这里
}
### 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);