Ideone.com

download

<?php
 
error_reporting(-1);
 
$amount = 240;
 
$bills = array(
	10 => 10,
	50 => 10,
	100 => 10,
	500 => 10,
);
 
$keysBills = array_keys($bills);
 
$attempts = 0;
 
function countBillsSum($billsCopy) {
 
	$valuesBillsCopy = array_values($billsCopy);
	$keysBillsCopy = array_keys($billsCopy);
 
	for($i = 0; $i < count($billsCopy); $i++) {
		$result[$i] = $valuesBillsCopy[$i] * $keysBillsCopy[$i];
	}	
	$result = array_sum($result);
	return $result;	
}	
 
function findChange($amount, $keysBills, $bills, $billNumber) {
 
	$debugOffset = str_repeat("  ", 3 - $billNumber);
	echo "{$debugOffset}enter $billNumber\n";
 
	global $attempts;
 
	$currentBill = $keysBills[$billNumber];
 
	$currentMaxBills = min(floor($amount / $keysBills[$billNumber]), $bills[$currentBill]);
 
	for ($i = $currentMaxBills; $i >= 0; $i--) {
 
		$attempts++;
		$billsCopy = $bills;
		$billsCopy[$currentBill] = $i;
 
		$sum = countBillsSum($billsCopy);
		echo "{$debugOffset}  i=$i, bills ".implode(", ", $billsCopy).", sum=$sum\n";
 
		if ($billNumber > 0) { 
			findChange($amount, $keysBills, $billsCopy, $billNumber - 1);
		} elseif (countBillsSum($billsCopy) == $amount) {
			echo "{$debugOffset}  MATCH ".implode(", ", array_values($billsCopy))." (sum=$sum)\n";
			break;
		} 
	}
	echo "{$debugOffset}end\n";
	return;
}
 
echo findChange($amount, $keysBills, $bills, 3);
 
//echo selectMinimumBillsArray(findChange($amount, $keysBills, $bills, 0, array()));
 
echo "\n".$attempts;

Success #stdin #stdout 0.01s 20568KB

stdin

Standard input is empty

stdout

enter 3
  i=0, bills 10, 10, 10, 0, sum=1600
  enter 2
    i=2, bills 10, 10, 2, 0, sum=800
    enter 1
      i=4, bills 10, 4, 2, 0, sum=500
      enter 0
        i=10, bills 10, 4, 2, 0, sum=500
        i=9, bills 9, 4, 2, 0, sum=490
        i=8, bills 8, 4, 2, 0, sum=480
        i=7, bills 7, 4, 2, 0, sum=470
        i=6, bills 6, 4, 2, 0, sum=460
        i=5, bills 5, 4, 2, 0, sum=450
        i=4, bills 4, 4, 2, 0, sum=440
        i=3, bills 3, 4, 2, 0, sum=430
        i=2, bills 2, 4, 2, 0, sum=420
        i=1, bills 1, 4, 2, 0, sum=410
        i=0, bills 0, 4, 2, 0, sum=400
      end
      i=3, bills 10, 3, 2, 0, sum=450
      enter 0
        i=10, bills 10, 3, 2, 0, sum=450
        i=9, bills 9, 3, 2, 0, sum=440
        i=8, bills 8, 3, 2, 0, sum=430
        i=7, bills 7, 3, 2, 0, sum=420
        i=6, bills 6, 3, 2, 0, sum=410
        i=5, bills 5, 3, 2, 0, sum=400
        i=4, bills 4, 3, 2, 0, sum=390
        i=3, bills 3, 3, 2, 0, sum=380
        i=2, bills 2, 3, 2, 0, sum=370
        i=1, bills 1, 3, 2, 0, sum=360
        i=0, bills 0, 3, 2, 0, sum=350
      end
      i=2, bills 10, 2, 2, 0, sum=400
      enter 0
        i=10, bills 10, 2, 2, 0, sum=400
        i=9, bills 9, 2, 2, 0, sum=390
        i=8, bills 8, 2, 2, 0, sum=380
        i=7, bills 7, 2, 2, 0, sum=370
        i=6, bills 6, 2, 2, 0, sum=360
        i=5, bills 5, 2, 2, 0, sum=350
        i=4, bills 4, 2, 2, 0, sum=340
        i=3, bills 3, 2, 2, 0, sum=330
        i=2, bills 2, 2, 2, 0, sum=320
        i=1, bills 1, 2, 2, 0, sum=310
        i=0, bills 0, 2, 2, 0, sum=300
      end
      i=1, bills 10, 1, 2, 0, sum=350
      enter 0
        i=10, bills 10, 1, 2, 0, sum=350
        i=9, bills 9, 1, 2, 0, sum=340
        i=8, bills 8, 1, 2, 0, sum=330
        i=7, bills 7, 1, 2, 0, sum=320
        i=6, bills 6, 1, 2, 0, sum=310
        i=5, bills 5, 1, 2, 0, sum=300
        i=4, bills 4, 1, 2, 0, sum=290
        i=3, bills 3, 1, 2, 0, sum=280
        i=2, bills 2, 1, 2, 0, sum=270
        i=1, bills 1, 1, 2, 0, sum=260
        i=0, bills 0, 1, 2, 0, sum=250
      end
      i=0, bills 10, 0, 2, 0, sum=300
      enter 0
        i=10, bills 10, 0, 2, 0, sum=300
        i=9, bills 9, 0, 2, 0, sum=290
        i=8, bills 8, 0, 2, 0, sum=280
        i=7, bills 7, 0, 2, 0, sum=270
        i=6, bills 6, 0, 2, 0, sum=260
        i=5, bills 5, 0, 2, 0, sum=250
        i=4, bills 4, 0, 2, 0, sum=240
        MATCH 4, 0, 2, 0 (sum=240)
      end
    end
    i=1, bills 10, 10, 1, 0, sum=700
    enter 1
      i=4, bills 10, 4, 1, 0, sum=400
      enter 0
        i=10, bills 10, 4, 1, 0, sum=400
        i=9, bills 9, 4, 1, 0, sum=390
        i=8, bills 8, 4, 1, 0, sum=380
        i=7, bills 7, 4, 1, 0, sum=370
        i=6, bills 6, 4, 1, 0, sum=360
        i=5, bills 5, 4, 1, 0, sum=350
        i=4, bills 4, 4, 1, 0, sum=340
        i=3, bills 3, 4, 1, 0, sum=330
        i=2, bills 2, 4, 1, 0, sum=320
        i=1, bills 1, 4, 1, 0, sum=310
        i=0, bills 0, 4, 1, 0, sum=300
      end
      i=3, bills 10, 3, 1, 0, sum=350
      enter 0
        i=10, bills 10, 3, 1, 0, sum=350
        i=9, bills 9, 3, 1, 0, sum=340
        i=8, bills 8, 3, 1, 0, sum=330
        i=7, bills 7, 3, 1, 0, sum=320
        i=6, bills 6, 3, 1, 0, sum=310
        i=5, bills 5, 3, 1, 0, sum=300
        i=4, bills 4, 3, 1, 0, sum=290
        i=3, bills 3, 3, 1, 0, sum=280
        i=2, bills 2, 3, 1, 0, sum=270
        i=1, bills 1, 3, 1, 0, sum=260
        i=0, bills 0, 3, 1, 0, sum=250
      end
      i=2, bills 10, 2, 1, 0, sum=300
      enter 0
        i=10, bills 10, 2, 1, 0, sum=300
        i=9, bills 9, 2, 1, 0, sum=290
        i=8, bills 8, 2, 1, 0, sum=280
        i=7, bills 7, 2, 1, 0, sum=270
        i=6, bills 6, 2, 1, 0, sum=260
        i=5, bills 5, 2, 1, 0, sum=250
        i=4, bills 4, 2, 1, 0, sum=240
        MATCH 4, 2, 1, 0 (sum=240)
      end
      i=1, bills 10, 1, 1, 0, sum=250
      enter 0
        i=10, bills 10, 1, 1, 0, sum=250
        i=9, bills 9, 1, 1, 0, sum=240
        MATCH 9, 1, 1, 0 (sum=240)
      end
      i=0, bills 10, 0, 1, 0, sum=200
      enter 0
        i=10, bills 10, 0, 1, 0, sum=200
        i=9, bills 9, 0, 1, 0, sum=190
        i=8, bills 8, 0, 1, 0, sum=180
        i=7, bills 7, 0, 1, 0, sum=170
        i=6, bills 6, 0, 1, 0, sum=160
        i=5, bills 5, 0, 1, 0, sum=150
        i=4, bills 4, 0, 1, 0, sum=140
        i=3, bills 3, 0, 1, 0, sum=130
        i=2, bills 2, 0, 1, 0, sum=120
        i=1, bills 1, 0, 1, 0, sum=110
        i=0, bills 0, 0, 1, 0, sum=100
      end
    end
    i=0, bills 10, 10, 0, 0, sum=600
    enter 1
      i=4, bills 10, 4, 0, 0, sum=300
      enter 0
        i=10, bills 10, 4, 0, 0, sum=300
        i=9, bills 9, 4, 0, 0, sum=290
        i=8, bills 8, 4, 0, 0, sum=280
        i=7, bills 7, 4, 0, 0, sum=270
        i=6, bills 6, 4, 0, 0, sum=260
        i=5, bills 5, 4, 0, 0, sum=250
        i=4, bills 4, 4, 0, 0, sum=240
        MATCH 4, 4, 0, 0 (sum=240)
      end
      i=3, bills 10, 3, 0, 0, sum=250
      enter 0
        i=10, bills 10, 3, 0, 0, sum=250
        i=9, bills 9, 3, 0, 0, sum=240
        MATCH 9, 3, 0, 0 (sum=240)
      end
      i=2, bills 10, 2, 0, 0, sum=200
      enter 0
        i=10, bills 10, 2, 0, 0, sum=200
        i=9, bills 9, 2, 0, 0, sum=190
        i=8, bills 8, 2, 0, 0, sum=180
        i=7, bills 7, 2, 0, 0, sum=170
        i=6, bills 6, 2, 0, 0, sum=160
        i=5, bills 5, 2, 0, 0, sum=150
        i=4, bills 4, 2, 0, 0, sum=140
        i=3, bills 3, 2, 0, 0, sum=130
        i=2, bills 2, 2, 0, 0, sum=120
        i=1, bills 1, 2, 0, 0, sum=110
        i=0, bills 0, 2, 0, 0, sum=100
      end
      i=1, bills 10, 1, 0, 0, sum=150
      enter 0
        i=10, bills 10, 1, 0, 0, sum=150
        i=9, bills 9, 1, 0, 0, sum=140
        i=8, bills 8, 1, 0, 0, sum=130
        i=7, bills 7, 1, 0, 0, sum=120
        i=6, bills 6, 1, 0, 0, sum=110
        i=5, bills 5, 1, 0, 0, sum=100
        i=4, bills 4, 1, 0, 0, sum=90
        i=3, bills 3, 1, 0, 0, sum=80
        i=2, bills 2, 1, 0, 0, sum=70
        i=1, bills 1, 1, 0, 0, sum=60
        i=0, bills 0, 1, 0, 0, sum=50
      end
      i=0, bills 10, 0, 0, 0, sum=100
      enter 0
        i=10, bills 10, 0, 0, 0, sum=100
        i=9, bills 9, 0, 0, 0, sum=90
        i=8, bills 8, 0, 0, 0, sum=80
        i=7, bills 7, 0, 0, 0, sum=70
        i=6, bills 6, 0, 0, 0, sum=60
        i=5, bills 5, 0, 0, 0, sum=50
        i=4, bills 4, 0, 0, 0, sum=40
        i=3, bills 3, 0, 0, 0, sum=30
        i=2, bills 2, 0, 0, 0, sum=20
        i=1, bills 1, 0, 0, 0, sum=10
        i=0, bills 0, 0, 0, 0, sum=0
      end
    end
  end
end

154

Discover > Sphere Engine API

Discover > IDE Widget

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language