Problem with calculating possibilities

[Dever1954]

Hi everybody,
since I got great help concerning my last question I decided to post my other problem here as well.
The task is to write a program which calculates how many possibilities of putting a certain number of bottles into boxes exist. It is allowed for a box to have 0 bottles in it, but there mustn't be any bottle left.

 #include <iostream>
	#include <vector>
	#include <cstdlib>

	std::vector<int> SizeOfBox;

	int Calculation(int remainingBottles,int remainingBoxes, int SpacesAvaiable);
	 

	int main()

	{
    int x, bottles, boxes, possibilities, SpacesAvaiable = 0;

	    std::cout << "Please input the number of bottles: \n";
	    std::cin >> bottles;
	    std::cout << "Please input the number of boxes:\n";
	    std::cin >> boxes;
	    std::cout << "Last but not least tell me the capacities of the boxes:\n";

	 

	    for (int i = 0; i < boxes; ++i)

	    {

	        std::cin >> x;
	        SizeOfBox.push_back(x);
	        SpacesAvaiable += x;

	    }

	    possibilities = Calculation(bottles,boxes,SpacesAvaiable);
	    std::cout << "There are " << possibilities << " possibilities!\n\n";
	    system("pause");
	    return 0;

	}

	 

	int Calculation(int remainingBottles, int remainingBoxes, int SpacesAvaiable)

	{     

    int i = 0;

	    int possibilities = 0;

	    while (i < SizeOfBox.size())

	    {

	       for (int j = 0; j < SizeOfBox[i]; j++)

	        {

	            if (remainingBottles >= remainingBoxes && remainingBottles -j <= SpacesAvaiable - SizeOfBox[i])
	            {

	                possibilities++;
	                SpacesAvaiable--;
	                remainingBottles--;

	            }

	         }

	        remainingBoxes--;
	        i++;
	    }

	    return possibilities;

	}

The problem is that for bottles = 7, boxes = 3, size1 = 2, size2 = 3, size3 =4 the correct answer is being given (6) but for e.g. bottles = 10, boxes = 3, size1 = 5, size2 = 8, size3 = 10 the answer the program gives is 10 whereas it should be a lot more.

Could anybody please have a look at my code and tell me what's wrong?
Thanks in advance,
Costa

[Chervil]

I'm not sure that a nested loop is a suitable approach to solve this problem (though it may be). I started thinking in terms of a recursive approach, something like, allocate some bottles to the first box, then the problem simplifies to how to distribute the remaining bottles among the remaining boxes. Have this function call itself until there are no bottles left. That's just a sketchy outline of an idea, it needs more work.

[Dever1954]

Have this function call itself until there are no bottles left.

That's an approach for one possibilit, but how would the function know that it checked all possible combinations?

[Chervil]

how would the function know that it checked all possible combinations

I hinted at it in my rather vague, "allocate some bottles to the first box". If I expand that a little, use a loop where each possible number of bottles (including zero) is allocated to the first box. I did try coding this, it was untidy and not very presentable, but it did seem to generate the same list of 48 possibilities that I arrived at by hand for your second example.

[Dever1954]

I can't really follow you, not because of your description but because I don't seem to understand the whole thing right.
I know that posting untidy code isn't a thing for most programmers (me included!) so would you mind sending what you've written to me as a private message so that I can have a look at it?
I'd classify myself as a rather advanced c++ programmer, but there are topics which I simply can't really grasp by mere description...
I'd like to thank you in advance if you agree with this and would like to apologize if you feel harassed by me ;).

[Chervil]

Hi - please check your messages.