签约棒球运动员

假设你是一支棒球大联盟球队的总经理。在赛季休季期间,你需要签入一些自由球员。球队老板给你的预算为X美元,你可以使用少于X美元来签入球员,但如果超支,球队老板就会解雇你。

你正在考虑在N个不同位置签入球员,在每个位置上,有P个该位置的自由球员供你选择。由于你不希望任何位置过于臃肿,因此每个位置最多签入一名球员(如果在某个特定位置上你没有签入任何球员,则意味着计划继续使用现有球员)。

为了确定一名球员的价值,你决定使用一种称为“VORP”,或“球员替换价值”的统计评价指标。球员的VORP值越高,其价值越高。但VORP值高的球员签约费用并不一定比VORP值低的球员高,因为还有球员价值之外的因素影响签约费用。

对于每个可选择的自由球员,你知道他的三方面信息:

1.他打哪个位置。2.他的签约费用。3.他的VORP。

设计一个球员选择算法,是的总签约费用不超过X美元,而球员的总VORP最大。你可以假定每位球员的签约费用是10万美元的整数倍。算法应输出签约球员的总VORP值,总签约费用,以及球员名单。分析算法的时间和空间复杂度。

算法设计与分析

01

状态转移函数如下:

vorp.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <ctime>
#include <iostream>
using namespace std;

#define n 10

struct player
{
int cost; //雇佣球员的花费,相当于背包问题中物品的容量(体积)
int vorp; //球员的价值,相当于背包问题中物品的价值
};

void candidate_vorp(player **candidate,int N,int P,int TOTAL) //TOTAL表示背包总重量
//player[N][P] 在N个不同位置上,有P个球员供你选择
//表示背包的数据value[position i][package capacity],即背包的总价值
//who[position i][package capacity]用来储存这个容量的背包,这个位置的放置情况
{
int **value,**who;
value=new int *[N+1];
for(int i=0;i<N+1;i++)
value[i]=new int[TOTAL];

who=new int *[N+1];
for(int i=0;i<N+1;i++)
who[i]=new int[TOTAL];

for(int x=0;x<=TOTAL;x+=10)
//x为此时的total cost,背包总价值
{
//初始化value[N][x],表示在这个容量下背包的放置情况
value[N][x]=-0x7fffffff;
who[N][x]=0;
for(int j=0;j<=P;j++)
{
if(candidate[N][j].cost<=x && candidate[N][j].vorp>value[N][x])
{
value[N][x]=candidate[N][j].vorp;
who[N][x]=j; //表示value[N][x]这个位置,选择的球员编号是第N个位置,第j号球员
}
}
}

//对剩下的N-1个位置进行放置
for(int i=N-1;i>=1;i--)
{
for(int x=0;x<=TOTAL;x+=10)
{
value[i][x]=value[i+1][x];
who[i][x]=0;

for(int j=0;j<=P;j++)
//j=0表示现有球员,不用替换球员,j=P表示替换成P位置的球员
//candidate[i][j]表示第i个位置第j个球员
{
if(x-candidate[i][j].cost>=0 && value[i][x]<candidate[i][j].vorp+value[i+1][x-candidate[i][j].cost])
//从第i+1个位置到第i个位置的时候,是否放入candidate[i][j]这个候选人?
//value[i+1][x-candidate[i][j].cost]表示背包的容量减小了,此时i+1 position --> i position
//加上candidate[i][j].corp值
{
value[i][x]=candidate[i][j].vorp+value[i+1][x-candidate[i][j].cost];
who[i][x]=j; //此时选择的是第j号球员
}
}
}
}
cout<<"Max value is : "<<value[1][TOTAL]<<endl;

int amount=TOTAL; //用一个变量保存总费用
for(int i=1;i<=N;i++)
{
int k=who[i][amount]; //位置为i,费用不超过amount的球员k
if(k!=0)
{
cout<<"No. "<<i<<" position "<<"No. "<<k<<"candidate->";
amount=amount-candidate[i][k].cost;
}
//循环结束的时候 amount表示剩下多少钱?花掉多少钱用总价减去amount
}

cout<<"The total money spent is "<<TOTAL-amount<<endl;

}

vorp.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include "vorp.h"

int main()
{
player **candidate;
int N=10,P=8,TOTAL=300;

candidate=new player*[N+1];
for(int i=0;i<=N;i++)
candidate[i]=new player[P+1];

for(int i=0;i<=N;i++)
{
for(int j=0;j<=P;j++)
{
candidate[i][j].cost=10*(j+1);
candidate[i][j].vorp=rand()%300;
}
}

candidate_vorp(candidate,N,P,TOTAL);

for(int i=0;i<=N;i++)
{
delete []candidate[i];
}
delete []candidate;
}

运行结果

02