題目
一塊金條切成兩半，是需要花費和長度數值一樣的銅板的，比如長度為20的金條，不管怎么切，都要花費20個銅板，一群人想整分整塊金條，怎么分最省銅板?
例如，給定陣列{10,20,30}，代表一共三個人，整塊金條長度為60，金條要分成10，20, 30三個部分，如果先把長度60的金條分成10和50，花費60；再把長度50的金條分成20和30，花費50；一共花費110銅板，但如果先把長度60的金條分成30和30，花費60；再把長度30金條分成10和20，花費30；一共花費90銅板，輸入一個陣列，回傳分割的最小代價，
貪心演算法最常用的兩個套路是堆跟排序，一般貪心演算法的核心代碼都很少，所以很少在筆試時候要你用貪心來解決某個問題，如果用暴力解通過對數器來驗證貪心的正確性就另說了，但是跟貪心有關的核心代碼都很少，
package com.harrison.class09;
import java.util.PriorityQueue;
public class Code04_LessMoneySplitGold {
// 貪心解法
public static int lessMoney1(int[] arr) {
PriorityQueue<Integer> pQ = new PriorityQueue<>();
for (int i = 0; i < arr.length; i++) {
pQ.add(arr[i]);
}
int cur = 0;
int sum = 0;
while (pQ.size() > 1) {
cur = pQ.poll() + pQ.poll();
sum += cur;
pQ.add(cur);
}
return sum;
}
// 純暴力！
public static int lessMoney2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
return process2(arr, 0);
}
// 等待合并的數都在arr里，pre之前的合并行為產生了多少總代價
// arr中只剩一個數字的時候，停止合并，回傳最小的總代價
public static int process2(int[] arr, int pre) {
if (arr.length == 1) {
return pre;
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
ans = Math.min(ans, process2(copyAndMergeTwo(arr, i, j), pre + arr[i] + arr[j]));
}
}
return ans;
}
public static int[] copyAndMergeTwo(int[] arr, int i, int j) {
int[] ans = new int[arr.length - 1];
int ansi = 0;
for (int arri = 0; arri < arr.length; arri++) {
if (arri != i && arri != j) {
ans[ansi++] = arr[arri];
}
}
ans[ansi] = arr[i] + arr[j];
return ans;
}
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * (maxValue + 1));
}
return arr;
}
public static void main(String[] args) {
int testTime = 100000;
int maxSize = 6;
int maxValue = 1000;
for (int i = 0; i < testTime; i++) {
int[] arr = generateRandomArray(maxSize, maxValue);
if (lessMoney1(arr) != lessMoney2(arr)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/386649.html
標籤：其他