数据结构练习——派多少人挖金矿问题

5.有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。每座金矿要么全挖，要么不挖,不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿?

方法 穷举法

列出所有的可能并尽量排除不可能的可能，最后比较这些可能的结果。
总人数为10，第一步要从中找出可以所有组合人数为10或小于10的结果，然后找出这些结果所带来的金币的最大值。此题的难点就在于，如何找出所有的可能，特别是金矿数越来越多的情况。

解决方案：二叉树

以上题为例，找出【3，3,4，5,5】的所有可能结果，转化为从最高的值作为头结点，列出所有的数，在 一条路径中，凡是出现过的数都要从数组中剔除，保证不重复。

1.以最高的5为头结点，得到如下四个数组（先不考虑相同的排除问题）

2.第二次循环 将数组中的5删掉，找出【3,3，4】的所有可能。

第三次循环 只剩下【3,3】的可能性
最后遍历整个二叉树，将每个数组的结果比较，得到最大值。

代码（Java）

import java.util.ArrayList;
import java.util.List;//存储金矿的属性
class JinKuang
{public int people;public int money;	public JinKuang(int people,int money){this.people=people;this.money=money;}
}// 二叉树class Tree{public int num;public int array;List<Tree> child_tree=new ArrayList<>();Tree(int num,int array){this.num=num;this.array=array;}
}public class test {
public static int total=10; //可用总人数
public static int MAX_money;//获得的最后金币
public static List<List<Integer>> result=new ArrayList<>();//存储所有可能数组的数组//折半排序法 人数从低到高，金币数高的排后
public static void sort(JinKuang[] jk){for (int i=0;i<jk.length;i++){for(int j=0;j<jk.length-i-1;j++){if(jk[j].people>jk[j+1].people){JinKuang m=jk[j];jk[j]=jk[j+1];jk[j+1]=m;}if(jk[j].people==jk[j+1].people && jk[j].money>jk[j+1].money){JinKuang m=jk[j];jk[j]=jk[j+1];jk[j+1]=m;}				}}}//得到一个金矿人数的数组
public static List<Integer> get_jk(JinKuang[] jk,int max)
{List<Integer> tree=new ArrayList<>();for(int i=0;i<=max;i++){tree.add(jk[i].people);}return tree;
}
//制造二叉树
public static Tree make_tree(JinKuang[] jk)
{Tree head=new Tree(-1,-1);	//头结点int max=jk.length-1;for(;max>=0;max--){//避免金矿人数重复情况while(max!=jk.length-1 && jk[max].people==jk[max+1].people){max--;if(max<0)return head;}//得到一个金矿人数的数组List<Integer> tree=get_jk(jk,max);//构造二叉树add_child(tree,total,head);		}	return head;
}
//运用递归添加子树
public static void add_child(List<Integer> tree,int total,Tree father)
{while(tree.size()!=0){int Max=tree.size()-1;Tree new_tree=new Tree(tree.get(Max),Max);tree.remove(Max);father.child_tree.add(new_tree);int this_total=total-new_tree.num;if(Max>0 && this_total>=tree.get(Max-1)){add_child(tree,this_total,new_tree);}}
}//方法重载，将二叉树的信息存入result
public static void look_tree(Tree head)
{for(int i=0;i<head.child_tree.size();i++){List<Integer> middle=new ArrayList<>();look_tree(head.child_tree.get(i),middle);}
}
public static void look_tree(Tree head,List<Integer> middle)
{middle.add(head.array);for(int i=0;i<head.child_tree.size();i++){List<Integer> middles=new ArrayList<>();middles.addAll(middle);look_tree(head.child_tree.get(i),middles);}if(!result.contains(middle))result.add(middle);}public static void  get_array(JinKuang[] jk)
{		Tree head=make_tree(jk);//将信息存入resultlook_tree(head);
}
//将最大金币值存入MAX_money中，并且返回路径
public static List<Integer> getMaxMoney(List<List<Integer>> result,JinKuang[] jk)
{List<Integer> re=null;for(List<Integer>a :result){int max_money=0;for(int money: a){max_money+= jk[money].money;}if(max_money>MAX_money){MAX_money=max_money;re=a;}}return re;
}
//主函数
public static void main(String[] args) {//初始化金矿信息JinKuang[] jk=new JinKuang[5];		jk[0] = new JinKuang(3,200);jk[1] = new JinKuang(4,300);jk[2] = new JinKuang(3,350);jk[3] = new JinKuang(5, 400);jk[4] = new JinKuang(5, 500);		//将金矿排序sort(jk);//构建二叉树以及将数据存入result中get_array(jk);List<Integer> re=getMaxMoney(result,jk);for(int a:re){System.out.println("选择的金矿为：人数:"+jk[a].people+",金币:"+jk[a].money);}System.out.println("最高获得的金币为:"+	MAX_money);
}

结果如下

方法未经测试，如有错误，请指正，谢谢！