湊硬幣問題
假設(shè)有 1 元，3 元，5 元的硬幣若干（無限）怕犁，現(xiàn)在需要湊出 11 元，問如何組合才能使硬幣的數(shù)量最少己莺？
用數(shù)組d來存儲當(dāng)前每個面值可以對應(yīng)的合成的最小數(shù)量
d(i) = d(j) + 1
這里 j < i奏甫。通俗地講，我們需要湊出 i 元凌受，就在湊出 j 的結(jié)果上再加上某一個硬幣就行了阵子。
那這里加上的哪個硬幣呢。把每個硬幣試一下就行了：
1.假設(shè)最后加上的是 1 元硬幣胜蛉，那 d(i) = d(j) + 1 = d(i - 1) + 1挠进。
2.假設(shè)最后加上的是 3 元硬幣色乾，那 d(i) = d(j) + 1 = d(i - 3) + 1。
3.假設(shè)最后加上的是 5 元硬幣领突，那 d(i) = d(j) + 1 = d(i - 5) + 1暖璧。
我們分別計算出 d(i - 1) + 1，d(i - 3) + 1君旦，d(i - 5) + 1 的值澎办，取其中的最小值，即為最優(yōu)解金砍，也就是 d(i)浮驳。
狀態(tài)轉(zhuǎn)移方程 d(i)=min{d(j)+1},if i>j
d(0)=0;
d(1)=1;
d(2)=d(1)+1=2;
d(3)=min{d(2)+1,d(0)+1}=1;
d(4)=min{d(3)+1,d(1)+1}=2;
d(5)=min{d(4)+1,d(2)+1,d(0)+1}=1;
d(6)=min{d(5)+1,d(3)+1,d(1)+1}=2;
public class test1430 {
private int[] d; // 儲存結(jié)果
private int[] coins = {1,3,5}; // 硬幣種類
private void d_func(int i, int num) {
if (i == 0) {
d[i] = 0;
d_func(i + 1, num);
}
else {
int min = 1000000; // 初始化一個很大的數(shù)值。當(dāng)最后如果得出的結(jié)果是這個數(shù)時捞魁，說明湊不出來。
for (int coin : coins) {
if (i >= coin && d[i - coin] + 1 < min) {//比較得到最小值
min = d[i - coin] + 1;
}
}
d[i] = min;
if (i < num) {
d_func(i + 1, num);
}
}
}
@Test
public void test() throws Exception {
int sum = 11; // 需要湊 11 元
d = new int[sum + 1]; // 初始化數(shù)組
d_func(0, sum); // 計算需要湊出 0 ～ sum 元需要的硬幣數(shù)量
for (int i = 0; i <= sum; i++) {
System.out.println("湊齊 " + i + " 元需要 " + d[i] + " 個硬幣");
}
}
}
當(dāng)測試數(shù)據(jù)換成3离咐、10谱俭、12.發(fā)現(xiàn)無法合成的數(shù)據(jù)也可以表示出來。因為其無法參與賦值宵蛀，所以結(jié)果還是設(shè)置的Min=1000000
思考：如果要求得需要的最大硬幣數(shù) 應(yīng)該如何處理
這里花了我好久的時間 感覺自己真的是蠢 智商不夠 想了一種方法 就是用t數(shù)組存最大數(shù)值昆著，然后每次和max比較，將最大的留下术陶。當(dāng)然考慮到有的沒辦法獲得凑懂，則沒辦法獲得的賦值為0。結(jié)合前面的進(jìn)行更改梧宫。寫的不好接谨，如果有好一點的方法希望能說一下。
private static int[] d; // 儲存結(jié)果
private static int[] t;
private static int[] coins = {3,5,6}; // 硬幣種類
private static void d_func_max(int i, int num) {
if (i == 0) {
d[i] = 0;
t[i]=0;
d_func_max(i + 1, num);
}
else {
int min = 1000000; // 初始化一個很大的數(shù)值塘匣。當(dāng)最后如果得出的結(jié)果是這個數(shù)時脓豪，說明湊不出來。
for (int coin : coins) {
if (i >= coin && d[i - coin] + 1 < min) {
min = d[i - coin] + 1;
}
}
d[i] = min;
int max=0;
for (int coin : coins) {
if(d[i]==1000000){
break;
}
if (i >= coin && t[i - coin] + 1 > max) {
max = t[i - coin] + 1;
}
}
t[i]=max;
if (i < num) {
d_func_max(i + 1, num);
}
}
}
public static void main(String[] args){
int sum = 12; // 需要湊 11 元
d = new int[sum + 1]; // 初始化數(shù)組
t= new int[sum+1];
d_func_max(0, sum); // 計算需要湊出 0 ～ sum 元需要的硬幣數(shù)量
for (int i = 0; i <= sum; i++) {
System.out.println("湊齊 " + i + " 元最多需要"+t[i] + " 個硬幣");
}
}
}
測試數(shù)據(jù)3忌卤、5扫夜、6。結(jié)果如圖
