自從受傷之后好久都打不起精神，好在今天垚哥提醒了我，讓我一個人的時候就專心學習，跟朋友在一起的時候再玩。確實，一個人玩容易抑郁。

現(xiàn)在記錄一下國王與金礦的編程題目：

有一個國家發(fā)現(xiàn)了5座金礦，每座金礦的黃金儲量不同，需要參與挖掘的工人數(shù)也不同。參與挖礦工人的總數(shù)是10人。每座金礦要么全挖，要么不挖，不能派出一半人挖取一半金礦。要求用程序求解出，要想得到盡可能多的黃金，應該選擇挖取哪幾座金礦？

?gold[] = {400, 500, 200, 300, 350};?people[] = {5, 5, 3, 4, 3};

第一種就是暴力求解法，每一個金礦只有挖或者不挖的可能，一共2的n次方種情況；再把每種情況是否有員工不足篩選出來，最后求最大值。這種方法我試試自己用C++和Java寫一下

package com.cai.javase.test國王與金礦;public class MostGold0 {public static int Violence( int n, int worker, int[] gold, int [] people ) {/*** k是相當于二進制01011，反向表示每一塊金礦是否挖掘* g是挖得的金礦* p是用的人數(shù)*/int maxgold = 0, k, g, p;for ( int i = 0; i < Math.pow （ 2 ，n ）; i++ ) {k = i; g = 0; p = 0;for( int j = 0; j < n; j++ ) {if( k % 2 == 1 ) {//如果最后一位是1，則挖這塊礦石g += gold[j];p += people[j];}k = k / 2;//二進制轉換，右移一位 }if( p <= worker && g > maxgold)//如果用的人小于總人數(shù)且挖的金子大于最大金礦maxgold = g;}return maxgold;}public static void main(String[] args) {// TODO Auto-generated method stubint[] gold = {400, 500, 200, 300, 350};int[] people = {5, 5, 3, 4, 3};System.out.println(Violence(5, 10, gold, people));}}

好吧，其實自己還是不會寫，還是借鑒了網(wǎng)上的代碼

下面用C++再寫一遍：

#include<iostream> #include<math.h>using namespace std;int Violence ( int n, int worker, int Gold[], int People[]);int main(){int gold[] = {400, 500, 200, 300, 350};int people[] = {5, 5, 3, 4, 3};cout << Violence(5, 10, gold, people) << endl; }int Violence ( int n, int worker, int Gold[], int People[]){/*** k是相當于二進制01011，反向表示每一塊金礦是否挖掘* g是挖得的金礦* p是用的人數(shù)*/int k, maxGold, g, p;for( int i = 0; i < pow( 2 , n ); i++){k = i; g = 0; p = 0;for( int j = 0; j < n; j++){if ( k % 2 == 1 ){//如果最后一位是1，則挖這塊礦石g += Gold[j];p +=People[j];}k /= 2;//二進制轉換，右移一位}if ( p <= worker && g > maxGold)//如果用的人小于總人數(shù)且挖的金子大于最大金礦maxGold = g;}return maxGold; }

?

?

如果不在main函數(shù)前定義violence函數(shù)則會出現(xiàn)以下error: `Violence' was not declared in this scope|

如果不在頭文件加上math.h則會出現(xiàn)error: `pow' was not declared in this scope|，因為有pow函數(shù)

下面是遞歸算法，也就是算最后一塊挖和不挖所能得到的最大金礦；先把java代碼抄上來：

package com.cai.javase.test國王與金礦;public class MostGold {public static void main(String[] args) {// TODO Auto-generated method stubint[] gold = {400, 500, 200, 300, 350};int[] people = {5, 5, 3, 4, 3};System.out.println(getMostGold(5, 10, gold, people));}public static int getMostGold(int n, int worker, int[] g, int[] p) {if ( n > g.length )//n超過了金礦數(shù)System.out.println("fOQ");if ( n <= 1 && worker < p[0])//一個金礦沒工人挖了return 0;if ( n == 1 && worker >= p[0])//一個金礦有工人return g[0];if ( n > 1 && worker < p[n - 1])//不是第一塊，但是工人挖不了這一塊了，因為人不夠return getMostGold(n - 1, worker, g, p);return Math.max(getMostGold(n - 1, worker, g, p),(getMostGold(n - 1, worker - p[n - 1], g, p) + g[n - 1]));} }

再改成C++ 代碼：

#include<iostream> #include<cmath> using namespace std; int MostGold(int n, int goldNum, int worker, int Gold[], int people[]){ // cout << "正在挖第" << n << "塊金子" << endl;if ( n > goldNum )cout<<"FoQ That man!"<<endl;if ( n <= 1 && worker < people[0]){return 0;// cout << "第一塊金礦沒工人挖了返回0" << endl; }if ( n <= 1 && worker >= people[0]){return Gold[0];// cout << "有工人挖就返回第一塊金礦的金子數(shù)" << endl; }if ( n > 1 && worker < people[n - 1]){return MostGold( n - 1, goldNum, worker, Gold, people );// cout << "不是第一塊金子且人數(shù)足夠挖這塊，返回不挖這塊能得到的最大金子數(shù)" << endl; }int a = MostGold( n - 1, goldNum, worker, Gold, people);//不挖最后一塊所能得到的最大金子數(shù)int b = MostGold( n - 1, goldNum, worker - people[n - 1], Gold, people) + Gold [n - 1];//挖最后一塊所能得到的最大金子數(shù)// if( a > b ) // cout << "不挖這一塊" << endl; // else // cout << "挖出了第" << n << "塊金子" << endl;return max( a, b ); }int main(){int gold[] = {400, 500, 200, 300, 350};//20 cout << sizeof(gold) << endl;//5 cout << sizeof(gold) / sizeof(gold[0]) << endl;int people[] = {5, 5, 3, 4, 3};int GoldNum = sizeof(gold) / sizeof(gold[0]);cout << MostGold(5, GoldNum, 10, gold, people) << endl << endl; // cout << gold << endl << people << endl; }

java中的求數(shù)組長度函數(shù)是.lengh而C++中的是sizeof（）

改的時候發(fā)現(xiàn)了數(shù)組傳入函數(shù)之后用sizeof就測不出長度了，int類型的數(shù)組的sizeof永遠是4，所以要在傳入函數(shù)之前就把數(shù)組的長度求出來再放進函數(shù)。

而且不知道為什么要在最后加兩個endl或者最后一行不注解掉才能顯示出900，而且不加上就會變成病毒被殺。

int Violence ( int n, int worker, int Gold[], int People[])

轉載于:https://www.cnblogs.com/caiziqi/p/11454399.html

總結

以上是生活随笔為你收集整理的国王与金矿的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。