UVa1412 fund management

meaning of the title

Train of thought:

The basic idea of this question is clear. d(i,p) is used to express the maximum value of cash when the portfolio is p after i days.
In addition, it should be noted that whether the current cash is enough is not a DAG's longest / shortest path problem when considering buying stocks, because the existence of some edges u - > V depends on the shortest path value from the starting point to the point u. That is to say, this problem can't be "de defined" like the previous DAG problem: if d(i,p) is used to represent the portfolio as p, from the day i to the maximum cash value that can be owned at last, it will be found that the status can't be transferred at all.

  1. Fund combination status processed in 9-level system
  2. Status number, no need to encode or decode
  3. Brush table method
#include <cstdio>
#include <vector>
#include <map> 
#include <algorithm>
using namespace std;
const int INF = 1<<30;

const int maxn = 8;
const int maxm = 101;
const int maxstate = 15000; 

double c, price[maxn][maxm];
int m, n, kk;
char name[maxn][50];
int s[maxn], k[maxn];

vector< vector<int> > states; // states[i]: state I 
map< vector<int>, int > ID; // Number corresponding to status

// Number each status 
void dfs(int cur_stock, vector<int> &s, int total){
	if(cur_stock == n){
		ID[s] = states.size();
		states.push_back( s );
		return;
	}
	// Buy the current stock 
	for(int i = 0; i <= k[cur_stock] && total + i <= kk; ++i){
		s[cur_stock] = i;
		dfs(cur_stock + 1, s, total + i);
	}
} 

int buy_next[maxstate][maxn], sell_next[maxstate][maxn]; // Indicates the status number transferred to after "buy stock i" and "sell stock i" of status s respectively 
void init(){
	vector<int> s1(n);
	states.clear();
	ID.clear();
	// Give all stock status numbers 
	dfs(0, s1, 0);
	// Find buy? Next, sell? Next 
	for(int s = 0; s < states.size(); ++s){
		int total = 0;
		for(int i = 0; i < n; ++i) total += states[s][i];
		for(int i = 0; i < n; ++i){
			buy_next[s][i] = sell_next[s][i] = -1;
			// Buy the i share 
			if(states[s][i] < k[i] && total < kk){
				vector<int> newstate = states[s];
				++newstate[i];
				buy_next[s][i] = ID[newstate];
			}
			// Sale of the i share 
			if(states[s][i] > 0){
				vector<int> newstate = states[s];
				--newstate[i];
				sell_next[s][i] = ID[newstate];
			}
		} 
	}
}

double d[maxm][maxstate];
int opt[maxm][maxstate], pre[maxm][maxstate];
// The current time (day) state is s, and its operation op may affect the next state s2. If its decision is good, it should be updated in time 
void update(int day, int s, int s2, double v, int op){
	if(v > d[day+1][s2]){
		d[day+1][s2] = v;
		opt[day+1][s2] = op;
		pre[day+1][s2] = s;
	}
}
// Plan 
double dp(){
	// Initialization 
	for(int day = 0; day <= m; ++day)
		for(int s = 0; s < states.size(); ++s)
			d[day][s] = -INF;
	//printf("%d\n",states.size());
	d[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;
			// hold
			update(day, s, s, v, 0);
			for(int i = 0; i < n; ++i){
				if(buy_next[s][i] >= 0 && v >= price[i][day] - 1e-3) 
					update(day, s, buy_next[s][i], v - price[i][day], i+1); // buy ith stock
				if(sell_next[s][i] >= 0)
					update(day, s, sell_next[s][i], v + price[i][day], -i-1); // sell ith stock
			}
		}
	}
	return d[m][0];
}

void print_ans(int day, int s){
	if(day == 0) return;
	print_ans(day-1, pre[day][s]);
	if(opt[day][s] == 0) printf("HOLD\n");
	else if(opt[day][s] > 0) printf("BUY %s\n",name[opt[day][s]-1]);
	else printf("SELL %s\n",name[-opt[day][s]-1]);
}

/* 
Total number of test plans 
int cnt = 0;
void test(int cur, int total){
	if(cur == 8){
		++cnt;
		return;
	}
	for(int i = 0; i <= 8 && total+i <= 8; ++i){
		test(cur+1, total+i);
	}
}
*/

int main()
{
	//freopen("in.txt","r",stdin);
	// test(0,0);
	// Printf (""% d \ n ", CNT); output 12870, the total number of schemes does not exceed 15000 
	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;
}


Posted on Fri, 29 Nov 2019 23:31:14 -0800 by daveeboi