多重背包問題有兩種解法：

1. 按照背包問題的常規分析?式，仿照完全背包，第三維枚舉使?的個數；
2. 利??進制可以表??定范圍內整數的性質，轉化成01 背包問題。
   ?建議：并不是所有的多重背包問題都能??進制優化，?且優化版本的代碼很?。因此，如果時間復雜度允許的情況下，能不優化就不優化
   解法?：常規分析
3. 狀態表?：
   dp[i][j]表?：從前i 個物品中挑選，總重量不超過j 的情況下，最?的價值。
   dp[n][m]就是最終結果。
4. 狀態轉移?程：
   根據第i 個物品選的個數，可以分x[i] + 1種情況：
   a. 選0 個：價值為dp[i - 1][j] ；
   b. 選1 個：價值為dp[i - 1][j - w[i]] + v[i] ；
   c. 選2 個：價值為dp[i - 1][j - 2 × w[i]] + 2 × v[i] ；
   d. …
   e. 選x[i]個：價值為dp[i - 1][j - x[i] × w[i]] + x[i] × v[i] 。
   因為要的是最?價值，所以dp[i][j]等于上述所有情況的最?值。但是要注意j-k*w[i]要?于等于0，并且不能按照完全背包的?式優化。
5. 初始化：
   全部為0 就不影響最終結果
6. 填表順序：
   從上往下每??，每??從左往右

#include <bits/stdc++.h>
using namespace std;const int N = 110;int n, m;
int x[N], w[N], v[N];
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> x[i] >> w[i] >> v[i];for (int i = 1; i <= n; i++)for (int j = m; j >= 0; j--)for (int k = 0; k <= x[i] && k * w[i] <= j; k++){f[i][j] = max(f[i][j], f[i-1][j - k*w[i]] + k * v[i]);}cout << f[n][m] << endl;return 0;
}

空間優化：

#include <bits/stdc++.h>
using namespace std;const int N = 110;int n, m;
int x[N], w[N], v[N];
int f[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> x[i] >> w[i] >> v[i];for (int i = 1; i <= n; i++)for (int j = m; j >= 0; j--)for (int k = 0; k <= x[i] && k * w[i] <= j; k++){f[j] = max(f[j], f[j - k*w[i]] + k * v[i]);}cout << f[m] << endl;return 0;
}

解法?：轉化成01背包問題
優化?式：??進制將x[i]個物品分組。
連續的?進制數有?個性質，就是$2^0～2^k$能夠表?區間[1, 2^(k+1) - 1]??所有的整數。?如：

• 1, 2, 4, 8可以表?[1, 15]內所有的整數。具體原因可以參考整數的?進制表?，正好1, 2, 4, 8對應?進制表?中每?位的權值，所以排列組合起來就可以表?[1,15]內所有的整數。
• 同理1, 2, 4 就可以表?[1, 7]內所有的整數。
  根據這樣?個性質，我們就可以把x[i]拆成?些?進制數再加上多出來的數，這樣的?組數就可以表?[1,x[i]]內所有的整數，問題就變成了01背包
  ?如x[i] = 9，w[i] = 2, v[i] = 3 ：
• 9 = 1 + 2 + 4 + 2 ；
• 分成4 組，每組的重量和價值分別為(2, 3)、(4, 6)、(8, 12)、(4, 6)

#include <bits/stdc++.h>
using namespace std;const int N = 110 * 5;int n, m;
int w[N], v[N], pos;
int f[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++){int x, y, z; cin >> x >> y >> z;//2進制拆分int t = 1;while (x >= t){pos++;w[pos] = t * y;v[pos] = t * z;x -= t;t *= 2;}if (x) //處理剩余{pos++;w[pos] = x * y;v[pos] = x * z;}}//01背包for (int i = 1; i <= pos; i++)for (int j = m; j >= w[i]; j--)f[j] = max(f[j], f[j - w[i]] + v[i]);cout << f[m] << endl;return 0;
}

題意：每?種花可以選[0, a[i]]個，在總數恰好等于m 時的總?案數
正好是多重背包求?案數的模型，我們可以?多重背包的思考?式來解決這道題。

1. 狀態表?：
   dp[i][j]表?：從前i個花中挑選，正好擺放j 個花盆時的?案數。
2. 狀態轉移?程：
   根據第i 種花選的個數k(0 ≤ k ≤ min(j, a[i])) 分情況討論：

• 如果當前花選了k 盆，之前的花要去湊夠j - k 盆，總的?案數就是dp[i - 1][j - k] ；
• 因為要的是總?案數，所以最終結果應該是k 的變化過程中的狀態的總和。
  dp[i][j] = dp[i][j] + dp[i - 1][j - k]

3. 初始化：
   dp[0][0] = 1 ，相當于起始狀態，為了讓后續的填表有意義，不然全都是0 。
4. 填表順序：
   從上往下每??，每??從左往右。
   這道題就不能??進制優化，因為這道題的背包，限定條件和價值是??對應的，并且求的是?案數。如果??進制優化會統計多余的情況，?如：

• 有兩個物品，個數分別是3, 2 ，要湊成總和為4 。
• 拆分之后為(1, 2)、(1, 1) ，跑?遍01 背包之后，結果是 3 ，但是實際情況應該是2 。
• 原因是1,2,1被統計了2次。但是在實際情況?，第?個物品全選，第?個物品選1個，只屬于1種情況，?01背包的邏輯會統計兩次

#include <bits/stdc++.h>
using namespace std;const int N = 110, MOD = 1e6 + 7;int n, m;
int a[N];
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];f[0][0] = 1;for (int i = 1; i <= n; i++){for (int j = m; j >= 0; j--){for (int k = 0; k <= j && k <= a[i]; k++){f[i][j] = (f[i][j] + f[i-1][j-k]) % MOD;        }}}cout << f[n][m] << endl;return 0;
}

空間優化

#include <bits/stdc++.h>
using namespace std;const int N = 110, MOD = 1e6 + 7;int n, m;
int a[N];
int f[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];f[0] = 1;for (int i = 1; i <= n; i++){for (int j = m; j >= 0; j--){for (int k = 1; k <= j && k <= a[i]; k++){f[j] = (f[j] + f[j-k]) % MOD;        }}}cout << f[m] << endl;return 0;
}

單獨考慮k==0

#include <bits/stdc++.h>
using namespace std;const int N = 110, MOD = 1e6 + 7;int n, m;
int a[N];
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];f[0][0] = 1;for (int i = 1; i <= n; i++){for (int j = m; j >= 0; j--){f[i][j] = f[i-1][j];for (int k = 1; k <= j && k <= a[i]; k++){f[i][j] = (f[i][j] + f[i-1][j-k]) % MOD;        }}}cout << f[n][m] << endl;return 0;
}