How do I work out how many of each value in a column I would need to add up to a total value in excel?

Question

So say

A1 - A8 contain values 11, 120, 321, 435, 623, 765, 964, 1039, B1 Contains a value of 1375 how could use a formula or macro in excel to work out how many would be needed to get a value of at least B1

So in this example:
A8 + A3 + A2
or
A8 + A3 + A1 + A1

Is there any way of doing this?

Sorry so to give another example and make this a little clearer.

I have a car I want to buy for $35,000 I have bank note denominations of $10, $20, $100, $1,000 and $10,000 what combinations of notes would I need to make up the total value of this using the least number of notes.

A quick look at this would say 3 x $10,000 and 5 x $1,000 would be exactly right whereas 4 x $10,000 would be the smallest number of bills. I would like to be able to input any value and get either the smallest number of bills or an exact match however I think the smallest number of bills would be best.

Wes

Answer 1

Okay so I've knocked up some inefficient code to manage this (in PHP as it was the easiest testing environment).

    $w=array();
    $a=7000;
    $a1=$a;
    $b=array(10,100,500,750);/*9 x 750 + 2 x 100 + 10 x 5*/
    $t=$b;
    $r=0;
    $z=0;

    while ($r==0){
        $z++;
        $num1=0;
        $num2=0;
        if (count($t)>0){
            $c=max($t);
            array_pop ($t); 
        }else{
            $r=1;
        }
        $i=0;
        $d=0;
        $q=0;
        $e=0;
        $j=0;
        while ($q==0){
            if ($c>$a1){
                $num2=$a1;
                $q=1;
            }else{
                $num1=$a1 / $c; 
                $num2=$a1 % $c;
                $q=2;
            }
        }   
        if (($a1>$c) and ($num2==0)){
            //echo "f<br>";//$r=1;
            $w[$z][0]=intval($num1);
            $w[$z][1]=$num2;
            $w[$z][2]=$q;
            $w[$z][3]=$c;
            $r=1;
        }else{
            $w[$z][0]=intval($num1);
            $w[$z][1]=$num2;
            $w[$z][2]=$q;
            $w[$z][3]=$c;
            $a1=$num2;
        }
    }


    foreach ($w as $ww){
        echo $ww[0]."|".$ww[3]."<br>";
    }

So this would print

9|750

0|500

2|100

5|10

First number is the amount of times that an array value goes into the defined value. second number is which array value it is.

So 7000 = (9 x 750) + (2 x 100) + (5 x 10);

Took some thinking to work out what was needed. Any suggestions on making the code more efficient I would welcome!

Answer 2

I'm putting this as an answer, because the comment boxes are too small to contain this explanation.

Are you sure you just want to get a number, which is larger than B1? In that case, you just take Nx = roundup(B1/Ax), where x is any number from 1 to 8.
If you're interested getting that number in the least amount of calculations (minimising Nx), you need to set x=8 (assuming that the numbers A1-A8 are ordered in ascending order).
However, if you're interested in the sum, above B1, which is closest to B1 (which you seem to be looking for, based on your answers), then the link, provided by Cybernetic Nomad might be helpful.

In other words: please clarify your question.

Answer 3

Having looked through this again it doesn't quite get to a level I'm happy with especially as I'd like to look at weighting this as well so here is another option:

$w=array();
$dividend=455000000;
$remainder=$dividend;
$b=array(4100000,10000000,50000000,101000000);/*9 x 750 + 2 x 100 + 10 x 5*/
$b1=array(5,4.8,3.9,3.2);
$t=$b;
$r=0;
$y=0;
$z=count($t);
while ($z>0){
    $z--;
    $quotient=0;
    $remainder2=0;
    $divisor=$t[$z];
    $i=0;
    $d=0;
    $q=0;
    $e=0;
    $j=0;
    while ($q==0){
        if ($divisor>$remainder){
            $remainder2=$remainder;
            $q=1;
        }else{
            $quotient=$remainder / $divisor; 
            $remainder2=$remainder % $divisor;
            $q=2;
        }
    }   
    if ($remainder<$divisor){
        $w[$y][0]=intval($quotient);
        $w[$y][1]=$remainder2;
        $w[$y][2]=$q;
        $w[$y][3]=$divisor;
        $remainder=$remainder2;
    }else{
        if (($quotient>1) and ($z<count($t)-1)){
            $w[$y-1][0]++;
            $z=0;
            unset($w[$y]);
            $remainder2=0;
        }else{
            $w[$y][0]=intval($quotient);
            $w[$y][1]=$remainder2;
            $w[$y][2]=$q;
            $w[$y][3]=$divisor;
            $remainder=$remainder2;
        }

    }
    $y++;
}

if ($remainder2>0){
    $w[$y-1][0]++;
}


 $total=0;
 foreach ($w as $ww){
    echo $ww[0]."|".$ww[3]."<br>";
    $total+=$ww[0] * $ww[3];
}

echo $total."<br>";