NOIP2012普及組 擺花(多重背包）

小明的花店新開張，為了吸引顧客，他想在花店的門口擺上一排花，共 mm 盆。

通過調查顧客的喜好，小明列出了顧客最喜歡的 n 種花，從 1 到 n 标号。

為了在門口展出更多種花，規定第 i 種花不能超過 ai 盆，擺花時同一種花放在一起，且不同種類的花需按标号的從小到大的順序依次擺列。

試程式設計計算，一共有多少種不同的擺花方案。

輸入格式
第一行包含兩個正整數 n 和 m，中間用一個空格隔開。 

第二行有 nn 個整數，每兩個整數之間用一個空格隔開，依次表示 a1,a2,…,an。

輸出格式
輸出隻有一行，一個整數，表示有多少種方案。

注意：因為方案數可能很多，請輸出方案數對 1000007 取模的結果。

資料範圍
0<n,m≤100,
0≤ai≤100
輸入樣例：
2 4
3 2
輸出樣例：
2
           

(DP,多重背包問題,背包問題求方案數) O(n2a)
問題轉化：

将花盆數量看作背包容量；
将花看作物品，體積是1，第 i 種物品最多選 ai 個；
問題：将背包裝滿的方案數是多少？
這是典型的多重背包求方案數問題：

狀态表示：f[i, j] 表示前i個物品，總體積是j的方案數；
狀态計算：f[i, j] = f[i - 1, j] + f[i - 1, j - 1] + ... 
+ f[i - 1, j - a[i]]。
           

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, mod = 1000007;

int n, m;
int f[N];

int main()
{
    cin >> n >> m;

    f[0] = 1;
    for (int i = 0; i < n; i ++ )
    {
        int a;
        cin >> a;
        for(int j=m;j>=0;j--){
            for(int k=1;k<=min(a,j);k++){//從1開始
                f[j] = (f[j] + f[j - k]) % mod;//最開始的f[j]表示f[i-1][j-0];
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
}
           

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, mod = 1000007;

int n, m;
int f[N][N];

int main()
{
    cin >> n >> m;

    f[0][0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        int a;
        cin >> a;
        for(int j=0; j<=m; j++){
            for(int k=0;k<=min(a,j);k++){
                f[i][j] = (f[i][j] + f[i-1][j - k]) % mod;
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}