01背包的滾動數組優化

【題目描述】

經典0—1背包問題,有n個物品，編號為i的物品的重量為w[i]，價值為c[i]，現在要從這些物品中選一些物品裝到一個容量為m的背包中，使得背包內物體在總重量不超過m的前提下價值盡量大。

#include<iostream>
using namespace std;const int N = 3500, M = 12800;
int m, n, w[N], v[N], dp[M];
//狀態 dp[j] 前i件物品在背包容量不超過j的情況下的最大價值
//狀態轉移方程 if (j >= w[i]) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
int main() {cin >> n >> m;for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];//01背包的滾動數組優化for (int i = 1; i <= n; i++){for (int j = m; j >= w[i]; j--) //01背包滾動數組優化的時候，注意j要逆推{dp[j] = max(dp[j],dp[j-w[i]]+v[i]);}}cout << dp[m] << endl;return 0;
}

?完全背包

1268：【例9.12】完全背包問題

【題目描述】

設有n�種物品，每種物品有一個重量及一個價值。但每種物品的數量是無限的，同時有一個背包，最大載重量為M�，今從n�種物品中選取若干件(同一種物品可以多次選取)，使其重量的和小于等于M�，而價值的和為最大。

#include<iostream>
using namespace std;const int N = 30, M = 200;
int m, n, w[N], v[N], dp[M];
//狀態 dp[j] 前i種物品在背包容量不超過j的情況下的最大價值
//狀態轉移方程
/*
dp[j]=max{dp[j-0*w[i]]+0*v[i],dp[j-1*w[i]]+1*v[i],dp[j-2*w[i]]+2*v[i],dp[j-3*w[i]]+3*v[i],...dp[j-m/w[i]*w[i]]+m/w[i]*v[i]}
*/
int main() {cin >> m >> n;for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];//完全背包樸素版本for (int i = 1; i <= n; i++)for (int j = m; j >= 1; j--)for (int k = 1; k <= m / w[i]; k++)if(j>=k*w[i]) dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);cout <<"max=" << dp[m] << endl;return 0;
}

多重背包

1269：【例9.13】慶功會

【題目描述】

為了慶賀班級在校運動會上取得全校第一名成績，班主任決定開一場慶功會，為此撥款購買獎品犒勞運動員。期望撥款金額能購買最大價值的獎品，可以補充他們的精力和體力。

多重背包

特點：n種物品，每件物品有指定數量s[i]（真實數量上限：min(m/w[i],s[i])）

狀態?dp[j]?前i種物品在背包容量不超過j的情況下的最大價值

int main() { cin  >> n >> m;for (int i = 1; i <= n; i++) cin >> w[i] >> v[i]>>s[i];//多重背包樸素版本for (int i = 1; i <= n; i++)for (int j = m; j >= 1; j--)for (int k = 1; k <= min(m / w[i], s[i]); k++)//針對第i種物品，得到選k件的最優解if (j >= k * w[i]) dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);cout << dp[m] << endl;return 0;
}