We must pay D dollars. Unfortunately, we only have bills of two denominations: p1 dollars and p2 dollars. So, we want to overpay as little as possible. You will be given ints D, p1 and p2. Return the minimum number of dollars greater than or equal to D that can be paid with the given bills. Assume that we have an infinite supply of both p1 and p…

AmountApproximation.java

public class AmountApproximation {
	public static int approximate(int D, int p1, int p2){
		int max_p1=(int)(D/p1)+1;
		int max_p2=(int)(D/p2)+1;
		int min=Integer.MAX_VALUE;
		for(int i=0;i<=max_p1;i++){
			for(int j=0;j<=max_p2;j++){
				int sum=p1*i+p2*j;
				if(sum>=D && sum<min)
					min=sum;
			}
		}
		return min;
	}
}

AmountApproximationTest.java

public class AmountApproximationTest {
	@Test
	public void testApproximate() {
		assertEquals(18, AmountApproximation.approximate(17, 7, 9));
		assertEquals(20, AmountApproximation.approximate(17, 7, 13));
		assertEquals(21, AmountApproximation.approximate(21, 7, 13));
		assertEquals(43, AmountApproximation.approximate(37, 9, 17));
		assertEquals(287398, AmountApproximation.approximate(287341, 2345, 7253));
	}
}