UVA 1412 Fund Management(复杂状态的动态规划和指标函数值有关的状态转移)

小灰灰 2021-12-17 03:57 120阅读 0赞

## 题意：你有c（0.01≤c≤1e8）美元现金，但没有股票。给你m（1≤m≤100）天时间和n（1≤n≤8）支股票供你买卖，要求最后一天结束后不持有任何股票，且剩余的钱最多。买股票不能赊账，只能用现金买。已知每只股票每天的价格（0.01～999.99。单位是美元/股）与参数si和ki，表示一手股票是si（1≤si≤1e6）股，且每天持有的手数不能超过ki（1≤ki≤k），其中k为每天持有的总手数上限。   每天要么不操作，要么选一只股票，买或卖它的一手股票。c和股价均最多包含两位小数（即美分）。最优解保证不超过1e9。要求输出每一天的决策（HOLD表示不变，SELL表示卖，BUY表示买）。 ##

## 分析：参考紫书P288-P290，定义d\[i\]\[s\]：表示第i天手中股票的状态为s时手中的最大钱数，采用刷表法更新d\[i+1\]\[s'\] ，s'表示s经过出手或买进转移的状态。问题就变成了如何表示状况s？采用n元组的形式。但不能将一个n元组表示进d数组，这里的方法是离线dfs出全部状态并分别编号，得出状态与相连的关系buy\_next与sell\_next。那么d中的状态s就可以用一个整数表示了。另外输出也有一定的技巧，用到了prev 与 opt 数组，并用正负区别操作。 ##

## LRJ代码： ##

#include<bits/stdc++.h>
    using namespace std;
    
    const double INF = 1e30;
    const int maxn = 8;
    const int maxm = 100 + 5;
    const int maxstate = 15000;
    
    int m, n, s[maxn], k[maxn], kk;
    double c, price[maxn][maxm];
    char name[maxn][10];
    
    double d[maxm][maxstate];
    int opt[maxm][maxstate], prev[maxm][maxstate];    //配合输出print_ans 
    
    int buy_next[maxstate][maxn], sell_next[maxstate][maxn];
    vector<vector<int> > states;                     
    //states[i]代表一个标号为i的n元组  组信息用vector保存 //一个n元组带包手持各股票的数目 
    map<vector<int>, int> ID;                        //ID 是vector到序号的映射 
    
    void dfs(int stock, vector<int>& lots, int totlot) {  //dfs序构造states 
      if(stock == n) {              //新的n元组构造完成 
        ID[lots] = states.size();   //ID 
        states.push_back(lots);     //push 
      }
      else for(int i = 0; i <= k[stock] && totlot + i <= kk; i++) {   //在满足k[]与K的限制下如果可行则dfs下一stock 
        lots[stock] = i;
        dfs(stock+1, lots, totlot + i);    //回溯 写法 
      }
    }
    
    void init() {    //利用states离线建立状态之间的关系 
      vector<int> lots(n);
      states.clear();  //clear1 
      ID.clear();      //clear2 
      dfs(0, lots, 0);  //return states 
      for(int s = 0; s < states.size(); s++) {   //操作一个状态 
        int totlot = 0;
        for(int i = 0; i < n; i++) totlot += states[s][i];  //目前状态的所有股数 
        for(int i = 0; i < n; i++) {             //枚举在状态中改变的股票i 
          buy_next[s][i] = sell_next[s][i] = -1;   //初值-1 
          if(states[s][i] < k[i] && totlot < kk) { //如果buy可行 
            vector<int> newstate = states[s];
            newstate[i]++;
            buy_next[s][i] = ID[newstate];
          }
          if(states[s][i] > 0) {                //如果sell可行 
            vector<int> newstate = states[s];
            newstate[i]--;
            sell_next[s][i] = ID[newstate];
          }
        }
      }
    }
    
    void update(int day, int s, int s2, double v, int o) {  //刷表法 更新 
    //在第day天 在进行操作后 状况s转移到状况s2 转移后手中钱数为v
    //对|o|进行操作      //opt的正负用以区分操作 buy || sell 
      if(v > d[day+1][s2]) {      
        d[day+1][s2] = v;
        opt[day+1][s2] = o;    //: 得出 [][] 的最优操作 
        prev[day+1][s2] = s;   //: 得出 [][] 的最优前状况 
      }
    }
    
    double dp() {
      for(int day = 0; day <= m; day++)
        for(int s = 0; s < states.size(); s++) d[day][s] = -INF //边界设定 
    
      d[0][0] = c;          //第0天手持0手股票 手中有c的钱数 
      for(int day = 0; day < m; day++)              //枚举天数 
        for(int s = 0; s < states.size(); s++) {    //枚举手中股票的状态 
          double v = d[day][s];
          if(v < -1) continue;  //return 
    
          update(day, s, s, v, 0); // HOLD
          for(int i = 0; i < n; i++) {
            if(buy_next[s][i] >= 0 && v >= price[i][day] - 1e-3)       //s状态下要买股票i 
              update(day, s, buy_next[s][i], v - price[i][day], i+1); // BUY
            if(sell_next[s][i] >= 0)                                   //s状态下要卖股票i 
              update(day, s, sell_next[s][i], v + price[i][day], -i-1); // SELL
          }
        }
      return d[m][0];    //到了第m天 手中没有股票 //反对DP原问题的最大值 
    }
    
    void print_ans(int day, int s) {   //根据prev与opt递归输出解 
      if(day == 0) return;
      print_ans(day-1, prev[day][s]);
      if(opt[day][s] == 0) printf("HOLD\n");   //==0 
      else if(opt[day][s] > 0) printf("BUY %s\n", name[opt[day][s]-1]);  // >0 
      else printf("SELL %s\n", name[-opt[day][s]-1]);                    //<0 
    }
    
    int main() {
      int kase = 0;
      while(scanf("%lf%d%d%d", &c, &m, &n, &kk) == 4) {
        if(kase++ > 0) printf("\n");
    
        for(int i = 0; i < n; i++) {
          scanf("%s%d%d", name[i], &s[i], &k[i]);
          for(int j = 0; j < m; j++) { scanf("%lf", &price[i][j]); price[i][j] *= s[i]; }
        }
        init();
    
        double ans = dp();
        printf("%.2lf\n", ans);
        print_ans(m, 0);
      }
      return 0;
    }