多重背包問題 I
-
問題描述：
有 N 種物品和一個容量是 V 的背包，
第 ii 種物品最多有 si 件，每件體積是 vi，價值是 wi，
求解將哪些物品裝入背包，可使物品體積總和不超過背包容量，且價值總和最大，
輸出最大價值， -
跟前面的背包問題解題思路差不多，相比較于完全背包問題多出的限制條件是這里同一種物品的數量有所限制，推導式：
F[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i], ·····, f[i - 1][ j - s*v[i]] + s*w[i])
-
代碼示例（純暴力版動態規劃）：
#include<bits/stdc++.h> using namespace std; const int N = 1010; int f[N][N], v[N], w[N], s[N], n, m; int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++) scanf("%d%d%d", v + i, w + i, s + i); for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) for(int k = 0; k <= s[i] && k * v[i] <= j; k ++) f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);// f[i][j]儲存的是已類舉情況中的最大值，所以max的第一個引數是f[i][j]，f[i-1][j]未必是上一次回圈結果的最大值，所以不能用f[i-1][j] printf("%d", f[n][m]); return 0; } -
優化為一維陣列后：
f[j] = max(f[j], f[j - v[i]] + w[i], ······, f[j - s * v[i]] + s * w[i])
#include<bits/stdc++.h> using namespace std; const int N = 1010; int f[N], v[N], w[N], s[N], n, m; int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++) scanf("%d%d%d", v + i, w + i, s + i); for(int i = 1; i <= n; i ++) for(int j = m; j >= v[i]; j --) for(int k = 1; k <= s[i] && k * v[i] <= j; k ++) f[j] = max(f[j], f[j - k * v[i]] + k * w[i]); printf("%d", f[m]); return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/423142.html
標籤：其他