d682 - TOI2010 第三題：職棒簽約問題
題目描述
題目描述了職棒球隊在有限預算下，從多個位置的自由球員中選擇簽約，以最大化球隊戰力指數總和的問題。給定球隊預算、需要補強的位置數量、每個位置的球員資訊（簽約金額和戰力指數），求出在預算內能獲得的最大戰力指數總和。
解題思路
本題可以建模為一個多重背包問題。每個位置可以看作一個背包，預算為背包容量，每個位置的球員可以看作是背包中的物品，物品的重量是簽約金額，價值是戰力指數。由於有多個位置需要補強，因此需要對每個位置獨立地進行背包問題的求解，然後將所有位置的最大戰力指數總和加起來。
程式碼中，a[i][0] 和 a[i][1] 分別表示在容量為 i 的背包中，當前位置的最大戰力指數。程式碼使用動態規劃的方式，迭代地更新 a[i][1] 的值，a[i][1] 記錄的是容量為 i 時的最大戰力指數。外層迴圈遍歷每個位置，內層迴圈遍歷該位置的所有球員，然後再遍歷所有可能的背包容量，更新 a[i][1] 的值。最後，程式碼遍歷所有可能的背包容量，找到最大戰力指數。
複雜度分析
- 時間複雜度: O(N * P * M)
- 空間複雜度: O(M)
程式碼
#include <iostream>
using namespace std;
int m,n,p,a[10005][2];
int main(){
while(cin >> m >> n >> p){
int v,w,ans=0;
for(int i=0;i<=m;++i){
a[i][0]=a[i][1]=0;
}
for(int i=0;i<n;++i){
for(int j=0;j<p;++j){
cin >> v >> w;
for(int k=0;k<=m-v;++k){
if(a[k][0]||k==0){
a[k+v][1]=max(a[k][0]+w,max(a[k+v][0],a[k+v][1]));
//cout << a[k+v][1] << "\n";
}
}
}
for(int k=0;k<=m;++k){
a[k][0]=a[k][1];
}
}
for(int i=m;i>=0;--i){
ans=max(a[i][0],ans);
}
cout << ans << "\n";
}
}