学步园

You have several identical balls that you wish to place in several baskets. Each basket has the same maximum capacity. You are given an int baskets, the number of baskets you have. You are given an int capacity, the maximum capacity of each basket. Finally you are given an int balls, the number of balls to sort into baskets. Return the number of ways you can divide the balls into baskets. If this cannot be done without exceeding the capacity of the baskets, return 0.
Each basket is distinct, but all balls are identical. Thus, if you have two balls to place into two baskets, you could have (0, 2), (1, 1), or (2, 0), so there would be three ways to do this.
Definition

Class:
FillBaskets
Method:
countWays
Parameters:
int, int, int
Returns:
int
Method signature:
int countWays(int baskets, int capacity, int balls)
(be sure your method is public)

Constraints
-
baskets will be between 1 and 5, inclusive.
-
capacity will be between 1 and 20, inclusive.
-
balls will be between 1 and 100, inclusive.

Examples：

0)

2
20
2
Returns: 3
The example from the problem statement.

1)

3
20
1
Returns: 3
We have only 1 ball, so we must choose which of the three baskets to place it in.

2)

3
20
2
Returns: 6
We can place both balls in the same basket (3 ways to do this), or one ball in each of two baskets (3 ways to do this).

3)

1
5
10
Returns: 0
We have more balls than our basket can hold.

4)

4
5
10
Returns: 146

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

我的C++代码:

#include <iostream>
class Basket{
    private:

    public:
    int baskets,capacity,balls,count,i;
     Basket();
     ~Basket();
     int countWays(int baskets, int capacity, int balls);
     int getWay(int baskets,int ba[],int balls,int point,int p);
 };

#include "Basket.hpp"
using namespace std;
int temp[5][100][20][5]; //临时变量，用于剪枝以提高效率，第二维代表还有多少球没放入篮子，第三维代表此时篮子还成多少空间
//第四维代表每个篮子在剩下当前球数量下的解决方案数目

   Basket::Basket(){    //构造函数
   }

   Basket::~Basket(){   //析构函数
   }
int getWay(int baskets,int bac[],int balls,int point,int p){
       int i;
       int count=0;
       int ba[baskets];
       for(int i=0;i<5;i++) ba[i]=bac[i];
       ba[point]--;//空间减少1
       balls--;//球减少1
       if(balls==0) return 1;//如果球放完返回1
       for(i=point;i<baskets;i++){
           if(ba[i]==0)  continue;//如果箱子放满不再使用
           if(temp[p][balls][ba[i]][i]!=0)//如果已经存在该条路的解决方法则不再执行,节省时间
           count+=temp[p][balls][ba[i]][i];
           else
           {
            temp[p][balls][ba[i]][i]=getWay(baskets,ba,balls,i,p);
            count+=temp[p][balls][ba[i]][i];
           }

       }
       return count;
 }
  
int countWays(int baskets, int capacity, int balls){       
    int i;
    int count=0;
    int ba[5];
    for(i=0;i<baskets;i++)
         ba[i]=capacity;          //初始化每个箱子的大小
    for(i=0;i<baskets;i++){

        count+=getWay(baskets,ba,balls,i,i);
    }

    return count;
      }

     
int main(){
    Basket basket;
    int i,count;
    cin>>basket.baskets;
    cin>>basket.capacity;
    cin>>basket.balls;
    for(int i=0;i<basket.baskets;i++){
        for(int j=0;j<basket.balls;j++)
        for(int m=0;m<basket.capacity;m++)
        for(int k=0;k<basket.baskets;k++)
        temp[i][j][m][k]=0;
     }
    cout<<countWays(basket.baskets,basket.capacity,basket.balls)<<endl;    //获得解决方案总数并打印
    return 0;
 }