C語言實現撈魚問題

C語言實現撈魚問題

撈魚問題：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
,dp[bucketN][fishN]);
}