动态规划之签约棒球自由球员 - z84616995z的专栏 - 博客频道 - CSDN.NET


动态规划之签约棒球自由球员 - z84616995z的专栏 - 博客频道 - CSDN.NET
            假设你是一支棒球大联盟球队的总经理。在赛季休季期间,你需要签入一些自由球员。球队老板给你的预算为X美元,你可以使用少于X美元来签入球员,但如果超支,球队老板就会解雇你。
              你正在考虑在N个不同位置签入球员,在每个位置上,有P个该位置的自由球员供你选择。由于你不希望任何位置过于臃肿,因此每个位置最多签入一名球员(如果在某个特定位置上你没有签入任何球员,则意味着计划继续使用现有球员)。
              为了确定一名球员的价值,你决定使用一种称为"VORP",或"球员替换价值"的统计评价指标。球员的VORP值越高,其价值越高。但VORP值高的球员签约费用并不一定比VORP值低的球员高,因为还有球员价值之外的因素影响签约费用。
              对于每个可选择的自由球员,你知道他的三方面信息:
              1.他打哪个位置。2.他的签约费用。3.他的VORP。
              设计一个球员选择算法,是的总签约费用不超过X美元,而球员的总VORP最大。你可以假定每位球员的签约费用是10万美元的整数倍。算法应输出签约球员的总VORP值,总签约费用,以及球员名单。分析算法的时间和空间复杂度。
 思考与分析:这明显是一个改进的背包问题。不超过X美元,相当于背包的总容量。总VORP最大,相当于背包的总价值。每位球员的签约费用,相当于每件物品的重量。现在我们要给出在签约费用不超过X美元的前提下使总价值最大的球员选择方案。以0-1背包为背景的动态规划算法,我们可以给其改进一下,这里每个位置(相当于每件物品)有P个球员。那么我们要多加一个循环用于求在找到最大价值方案的前提下还要先找出P个球员之中的价值最大的那个。那么我们现在可以刻画出递归式。
递归式为:


     struct Player
06{//球员结构体
07    int cost;//雇佣球员的花费
08    int vorp;//球员的价值
09};
10void FREE_AGENT_VORP(struct Player **p,int N,int P,int X)
11{//采用从底到顶的顺序来设置v[i][j]的值
12   int **v,**who,i;
13   v=new int*[N+1];
14   for (  i=0;i<=N;i++)
15   {
16       v[i]=new int[X];
17   }
18   who=new int*[N+1];
19   for (  i=0;i<=N;i++)
20   {
21       who[i]=new int[X];
22   }
23   //二维数组v[i][j]代表位置i的不超过总费用j时的总价值(相当于背包的总价值)
24   //二维数组who[i][j]代表选择位置i的总费用不超过j的球员
25   for (int x=0;x<=X;x+=10)//10=10万
26   {//首先放v[n][x]
27       v[N][x]=-0x7fffffff;
28       who[N][x]=0;//x小于v[n][x],所对应的值设为0,否则就为可以放置
29       for (int k=0;k<=P;k++)
30       {
31           if (p[N][k].cost<=x&&p[N][k].vorp>v[N][x])
32           {
33               v[N][x]=p[N][k].vorp;
34               who[N][x]=k;
35           }
36       }
37   }
38   //对剩下的N-1个位置进行放置。 
39    for ( i=N-1;i>=1;i--)
40    {
41        for (int x=0;x<=X;x+=10)//x代表当前总费用(相当于当前总重量j)
42        {
43            v[i][x]=v[i+1][x];
44            who[i][x]=0;
45            for (int k=0;k<=P;k++)
46            {//注意k=0时是现有球员,k=0表示不用替换球员
47                //p[i][k].cost代表位置i的第k个球员的费用(相当于位置i的第k个物品重量)
48                //p[i][k].vorp代表位置i的第k个球员的价值(相当于位置i的第k个物品价值)
49                if (x-p[i][k].cost>=0&&v[i+1][x-p[i][k].cost]+p[i][k].vorp>v[i][x])
50                {//选择在总费用范围内的总价值最大的那个球员
51                    v[i][x]=v[i+1][x-p[i][k].cost]+p[i][k].vorp;
52                    who[i][x]=k;
53                }
54            }
55        }
56    }
57    cout<<"最大价值="<<v[1][X]<<endl;
58    int amt=X;//借用一个变量保存总费用(相当于总重量)
59    for ( i=1;i<=N;i++)
60    {
61        int k=who[i][amt];//位置i的费用为不超过amt费用的球员k
62        if (k!=0)//k非0时,说明要签约位置i的第k个球员
63        {
64            cout<<"第"<<i<<"个位置"<<"第"<<k<<"个人->";
65            amt-=p[i][k].cost;//签约了一个球员后,剩余的总费用。(相当于剩余的总重量)
66        }
67    }
68    cout<<"The total money spent is"<<X-amt<<endl;
69        
70}
Read full article from 动态规划之签约棒球自由球员 - z84616995z的专栏 - 博客频道 - CSDN.NET

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts