動態規劃之簽約棒球自由球員
假設你是一支棒球大聯盟球隊的總經理。在賽季休季期間，你需要簽入一些自由球員。球隊老板給你的預算為X美元，你可以使用少於X美元來簽入球員，但如果超支，球隊老板就會解雇你。
你正在考慮在N個不同位置簽入球員，在每個位置上，有P個該位置的自由球員供你選擇。由於你不希望任何位置過於臃腫，因此每個位置最多簽入一名球員(如果在某個特定位置上你沒有簽入任何球員，則意味著計劃繼續使用現有球員)。
為了確定一名球員的價值，你決定使用一種稱為“VORP”，或“球員替換價值”的統計評價指標。球員的VORP值越高，其價值越高。但VORP值高的球員簽約費用並不一定比VORP值低的球員高，因為還有球員價值之外的因素影響簽約費用。
對於每個可選擇的自由球員，你知道他的三方面信息：
1.他打哪個位置。2.他的簽約費用。3.他的VORP。
設計一個球員選擇算法，是的總簽約費用不超過X美元，而球員的總VORP最大。你可以假定每位球員的簽約費用是10萬美元的整數倍。算法應輸出簽約球員的總VORP值，總簽約費用，以及球員名單。分析算法的時間和空間復雜度。
思考與分析：這明顯是一個改進的背包問題。不超過X美元，相當於背包的總容量。總VORP最大，相當於背包的總價值。每位球員的簽約費用，相當於每件物品的重量。現在我們要給出在簽約費用不超過X美元的前提下使總價值最大的球員選擇方案。以0-1背包為背景的動態規劃算法，我們可以給其改進一下，這裡每個位置(相當於每件物品)有P個球員。那麼我們要多加一個循環用於求在找到最大價值方案的前提下還要先找出P個球員之中的價值最大的那個。那麼我們現在可以刻畫出遞歸式。
遞歸式為：
代碼如下：(本代碼注釋部分和背包相關問題做了一個對比，詳細的解釋了和背包問題的相似性，如果對背包問題有疑問可以打開上面的鏈接)
#include
#include
using namespace std;
#define n 10
struct Player
{//球員結構體
int cost;//雇傭球員的花費
int vorp;//球員的價值
};
void FREE_AGENT_VORP(struct Player **p,int N,int P,int X)
{//采用從底到頂的順序來設置v[i][j]的值
int **v,**who,i;
v=new int*[N+1];
for ( i=0;i<=N;i++)
{
v[i]=new int[X];
}
who=new int*[N+1];
for ( i=0;i<=N;i++)
{
who[i]=new int[X];
}
//二維數組v[i][j]代表位置i的不超過總費用j時的總價值(相當於背包的總價值)
//二維數組who[i][j]代表選擇位置i的總費用不超過j的球員
for (int x=0;x<=X;x+=10)//10=10萬
{//首先放v[n][x]
v[N][x]=-0x7fffffff;
who[N][x]=0;//x小於v[n][x],所對應的值設為0，否則就為可以放置
for (int k=0;k<=P;k++)
{
if (p[N][k].cost<=x&&p[N][k].vorp>v[N][x])
{
v[N][x]=p[N][k].vorp;
who[N][x]=k;
}
}
}
//對剩下的N-1個位置進行放置。
for ( i=N-1;i>=1;i--)
{
for (int x=0;x<=X;x+=10)//x代表當前總費用(相當於當前總重量j)
{
v[i][x]=v[i+1][x];
who[i][x]=0;
for (int k=0;k<=P;k++)
{//注意k=0時是現有球員，k=0表示不用替換球員
//p[i][k].cost代表位置i的第k個球員的費用(相當於位置i的第k個物品重量)
//p[i][k].vorp代表位置i的第k個球員的價值(相當於位置i的第k個物品價值)
if (x-p[i][k].cost>=0&&v[i+1][x-p[i][k].cost]+p[i][k].vorp>v[i][x])
{//選擇在總費用范圍內的總價值最大的那個球員
v[i][x]=v[i+1][x-p[i][k].cost]+p[i][k].vorp;
who[i][x]=k;
}
}
}
}
cout<<"最大價值="<";
amt-=p[i][k].cost;//簽約了一個球員後，剩余的總費用。(相當於剩余的總重量)
}
}
cout<<"The total money spent is"<總結：此算法運行時間為O(NXP),存儲容量為O(NX). 本問題類似背包問題，也可以說是背包問題的一個升級版，多了一重循環，但本質是一樣的。
