C语言实现捞鱼问题

浏览数：38 / 时间：2015年06月08日

捞鱼问题：20个桶，每个桶中有10条鱼，用网从每个桶中抓鱼，每次可以抓住的条数随机，每个桶只能抓一次，问一共抓到180条的排列有多少种。

分析：看看这个问题的对偶问题，抓取了180条鱼之后，20个桶中剩下了20条鱼，不同的抓取的方法就对应着这些鱼在20个桶中不同的分布，于是问题转化为将20条鱼分到20个桶中有多少中不同的分类方法（这个问题当然也等价于180条鱼分到20个桶中有多少种不同的方法）。

dp[i][j]：前i个桶放j条鱼的方法为前i-1个桶放j-k（0<=k<=10）（因为第i桶只能放0到10条鱼）条鱼的方法总和。我们可以得到状态方程：f(i,j) = sum{ f(i-1,j-k), 0<=k<=10}

/*捞鱼：将20条鱼放在20个桶中，每个桶最多可以放10条，求得所有的排列方法
/*自底向上DP f(i,j) = sum{ f(i-1,j-k), 0<=k<=10 }
/*该方法中测试 20个桶 180条鱼，与递归速度做对比
*/
void CatchFish()
{
    int dp[21][200]; // 前i个桶放j条鱼的方法数
    int bucketN = 20;
    int fishN = 20;
    memset(dp,0,sizeof(dp));
    for(int i = 0; i <= 10; ++i)  // 初始化合法状态
    {
        dp[1][i] = 1;
    }
    for(int i = 2; i <= bucketN; ++i)  // 从第二个桶开始
    {
        for(int j = 0; j <= fishN; ++j)
        {
            for(int k = 0; k <= 10 && j-k >= 0; ++k)
            {
                dp[i][j] += dp[i-1][j-k];
            }
        }
    }
    printf("%d\n",dp[bucketN][fishN]);
}