[Java] UVa 10626 Buying Coke

題目連結

題意:
一瓶可樂 $8
每組題目給定要買幾瓶、1元、5元、10元硬幣數量
每次只能買一瓶，找錢會以最少的硬幣數量
求使用最少硬幣的買法，輸出使用硬幣總數

例如:
2 2 1 1
表示要買 2 瓶、$1, $5, $10 分別有 2, 1, 1 個
我們知道，用最少的買法就是花 1 個 $10
所以用 $10 買了一瓶後，會找 2 個 $1
此時硬幣數分別為 4, 1, 0
還有一瓶，只能用 $5 *1  + $1 *3 (4 個硬幣)
所以總共使用 1 + 4 = 5 個硬幣

解法:
以陣列[n1][n5][n10] 表示
在硬幣數分別為n1, n5, n10 時
可以用來買飲料的最少硬幣數

分析任何可以買飲料的硬幣組合(括號表示使用硬幣數):
1. $10 (1) /找 $1 * 2
2. $10 + $1 * 3 (4) /找 $5 * 1
3. $5 * 2 (2) /找 $1 * 2
4. $5 * 1 + $1 * 3 (4)
5. $1 * 8 (8)

飲料一次只買一瓶
寫一個 dp，每次執行代表買一瓶
上述情況都比過一輪判斷最小情況

每次買完會找錢，陣列要開得比測資範圍大
另外注意每組測資前陣列值要初始化

程式(Java):

	import java.util.*;
	public class Main {
	// 500, 100, 50
	static int dp[][][];
	public static int buy(int n, int a, int b, int c) {
	if (n == 0)
	return 0;
	if (dp[a][b][c] != 0)
	return dp[a][b][c];
	dp[a][b][c] = Integer.MAX_VALUE;
	if (c >= 1)
	dp[a][b][c] = Math.min(dp[a][b][c], buy(n-1, a+2, b, c-1) + 1);
	if (a >= 3 && c >= 1)
	dp[a][b][c] = Math.min(dp[a][b][c], buy(n-1, a-3, b+1, c-1) + 4);
	if (b >= 2)
	dp[a][b][c] = Math.min(dp[a][b][c], buy(n-1, a+2, b-2, c) + 2);
	if (b >= 1 && a >= 3)
	dp[a][b][c] = Math.min(dp[a][b][c], buy(n-1, a-3, b-1, c) + 4);
	if (a >= 8)
	dp[a][b][c] = Math.min(dp[a][b][c], buy(n-1, a-8, b, c) + 8);
	return dp[a][b][c];
	}
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int t = sc.nextInt();
	while (t-- > 0) {
	dp = new int[800][200][100];
	int num = sc.nextInt();
	int n1 = sc.nextInt();
	int n5 = sc.nextInt();
	int n10 = sc.nextInt();
	System.out.println(buy(num, n1, n5, n10));
	}
	}
	}

view raw UVa10626.java hosted with ❤ by GitHub