UVA1412 基金管理 Fund Management题解

· · 题解

先看数据很小在 8 以内，那么肯定是状压 dp，很容易设出方程

dp(i,s)=\max(dp(i-1,s')+w,dp(i-1,s))

即考虑第 i 天，资产组合为 s 所得到的最大收益，由 i-1 天转移而来, w 为买或卖股票所得到或付出的钱，或者选择不操作。需要注意的是本题采用的是刷表法。那么这是一个九进制的状压，由于九进制无法像二进制那样快速操作，所以必须用到编码和解码，使程序效率大大降低。虽然程序会超时，但是这却是编码/解码的方法编写复杂状态动态规划的一个很好的样例，里面处理九进制的方法也值得学习，所以这里给出示范代码。


// 本程序会超时
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
using namespace std;
const double inf=1e30;
const int maxn=10;
const int maxm=110;
map<int,double> dp[maxm];
map<int,int> opt[maxm],prev[maxm];
int m,n,s[maxn],k[maxn],kk;
double c,price[maxn][maxm];
char name[maxn][10];
int encode(int* portfolio){//编码 por->h
    int h=0;
    for(int i=1;i<=n;i++) h=h*9+portfolio[i];//1->n 高位->低位 
    return h;
}
int decode(int h,int* portfolio){//解码  h->por
    int totlot=0;
    for(int i=n;i>=1;i--){
        portfolio[i]=h%9;
        totlot+=portfolio[i];
        h/=9;
    }
    return totlot;
}
void update(int oldh,int day,int h,double v,int o){
    if(dp[day].count(h)==0||v>dp[day][h]){//注意用count(h)，因为可能之前没映射 
        dp[day][h]=v;
        opt[day][h]=o;
        prev[day][h]=oldh;
    }
}
double Dp(){
    int portfolio[maxn];
    dp[1][0]=c;
    for(int day=1;day<=m;day++){
        for(map<int,double>::iterator it=dp[day].begin();it!=dp[day].end();it++){//迭代器 
            int h=it->first;
            double v=it->second;
            int totlot=decode(h,portfolio);
            update(h,day+1,h,v,0);
            for(int i=1;i<=n;i++){
                if(portfolio[i]<k[i]&&totlot<kk&&v>=price[i][day]-1e-3){
                    portfolio[i]++;
                    update(h, day+1, encode(portfolio),v-price[i][day],i);
                    portfolio[i]--;
                }
                if(portfolio[i]>0){
                    portfolio[i]--;
                    update(h,day+1,encode(portfolio),v+price[i][day],-i);
                    portfolio[i]++;
                }
            }
        }
    }
    return dp[m+1][0];
}
void print_ans(int day,int h){
    if(day==1) return ;
    print_ans(day-1,prev[day][h]);
    if(opt[day][h]==0) printf("HOLD\n");
    else if(opt[day][h]>0) printf("BUY %s\n",name[opt[day][h]]);
    else printf("SELL %s\n",name[-opt[day][h]]);
}
int main() {
    int kase=0;
    while(cin>>c>>m>>n>>kk){
        if(kase++>0) cout<<endl;
        for(int i=1;i<=n;i++){
            cin>>name[i]>>s[i]>>k[i];
            for(int j=1;j<=m;j++) { 
                cin>>price[i][j]; 
                price[i][j]*=s[i]; 
            }
        }
        for(int i=1;i<=m;i++){ dp[i].clear(); opt[i].clear(); prev[i].clear(); }
        double ans=Dp();
        printf("%.2lf\n",ans);
        print_ans(m+1,0);
    }
    return 0;
}

注意到虽然理论状态很多，但是实际可能满足题意的状态很少。故这里用到的思想就类似于 UVA12096 集合栈计算机 The SetStack Computer 这题了，我们可以提前计算出可能的所有状态并用 STL map，给他们编号，并且提前记录出下一个转移的对象，这样就可以大大提升程序效率了！

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
const int maxn=10;
const int maxm=110;
const int maxstate=15000;
const int inf=0x3f3f3f3f;
double c,price[maxn][maxm];
int n,m,kk,kase=0;
char name[maxn][15];
int k[maxn],s[maxn];
double dp[maxm][maxstate];
int buy_next[maxstate][maxn],sell_next[maxstate][maxn];
int pre[maxm][maxstate],op[maxm][maxstate];
map<vector<int>, int> ID;
vector<vector<int> > state;
void inp(){
    if(kase++) cout<<endl;
    for(int i=1;i<=n;i++){
        cin>>name[i]>>s[i]>>k[i];
        for(int j=1;j<=m;j++){
            cin>>price[i][j];
            price[i][j]*=s[i];
        }
    }
}
void dfs(int stock,vector<int>& lots,int totlot){
    if(stock==n+1){
        ID[lots]=state.size();
        state.push_back(lots);
        return ; 
    }
    for(int i=0;i<=k[stock]&&totlot+i<=kk;i++){
        lots[stock]=i;
        dfs(stock+1,lots,totlot+i);     
    }
}
void init(){
    vector<int> lots(n+10);
    state.clear();
    ID.clear();
    dfs(1,lots,0);
    for(int s=0;s<state.size();s++){
        int tot=0;
        for(int i=1;i<=n;i++) tot+=state[s][i];
        for(int i=1;i<=n;i++){
            buy_next[s][i]=sell_next[s][i]=-1;
            if(state[s][i]<k[i]&&tot<kk){
                vector<int> newstate=state[s];
                newstate[i]++;
                buy_next[s][i]=ID[newstate];
            }
            if(state[s][i]>0){
                vector<int> newstate=state[s];
                newstate[i]--;
                sell_next[s][i]=ID[newstate];   
            }
        }
    }
}
void update(int s1,int d2,int s2,double v,int val){
    if(v>dp[d2][s2]){
        dp[d2][s2]=v;
        pre[d2][s2]=s1;
        op[d2][s2]=val;
    }
}
void work(){
    for(int i=0;i<=m+1;i++)
        for(int j=0;j<state.size();j++) dp[i][j]=-inf;
    dp[1][0]=c;
    for(int d=1;d<=m;d++){
        for(int s=0;s<state.size();s++){
            double v=dp[d][s];
            if(v<-1) continue;
            update(s,d+1,s,v,0);
            for(int i=1;i<=n;i++){
                if(buy_next[s][i]>=0&&v>=price[i][d]-1e-3) update(s,d+1,buy_next[s][i],v-price[i][d],i);
                if(sell_next[s][i]>=0) update(s,d+1,sell_next[s][i],v+price[i][d],-i);
            }
        }
    }
    printf("%.2lf\n",dp[m+1][0]);
}
void print(int day,int st){
    if(day==1) return ;
    print(day-1,pre[day][st]);
    if(op[day][st]>0) cout<<"BUY "<<name[op[day][st]]<<endl;
    else if(op[day][st]==0) cout<<"HOLD"<<endl;
    else cout<<"SELL "<<name[-op[day][st]]<<endl;
}
int main(){
    while(cin>>c>>m>>n>>kk){
        inp();
        init();
        work();
        print(m+1,0);
    }
    return 0;
}