#include <iostream.h>
#include <math.h>
#include <conio.h>
struct SheepSell
{
int sellCount;
int remained_from_pre_stage;
int income;
};
void dynamicSolve(int years,int initialSheepCount,int *sheepCost)
{
int *temp_sell_index = new int[years];
int *solution_sell_index = new int[years];
int *sheepCountForEachYear = new int[years];
int *maxForEachYear = new int[years];
SheepSell **sell_ordder = new SheepSell*[years];
// init tables
for(int i=0;i<years;i++)
{
temp_sell_index[i] = (initialSheepCount*(int)pow(2,i));
sheepCountForEachYear[i] = initialSheepCount*(int)pow(2,i);
sell_ordder[i] = new SheepSell[sheepCountForEachYear[i]];
solution_sell_index[i] = 0;
maxForEachYear[i] = 0;
}
// init first year params
for(int i=0;i<initialSheepCount;i++)
{
SheepSell sp;
sp.sellCount = i;
sp.remained_from_pre_stage = initialSheepCount;
sp.income = i*sheepCost[0];
sell_ordder[0][i] = sp;
}
for(int i=1;i<years;i++)
{
std::cout << "we are at year " << i << "\n";
bool isLastYear = (i==years-1)? true:false;
int t = 0;
if(isLastYear)
t = 2;
else
t = 0;
for(int j=t;j<sheepCountForEachYear[i];)
{
SheepSell sp_temp;
sp_temp.sellCount = j;
sp_temp.income = 0;
for(int k=0;k<temp_sell_index[i-1];k++)
{
bool condition_ = false;
int sheep_count_from_remaind = (sell_ordder[i-1][k].remained_from_pre_stage-
sell_ordder[i-1][k].sellCount)*2;
int sheep_count_from_origin = (sheepCountForEachYear[i-1]-
sell_ordder[i-1][k].sellCount)*2;
if(isLastYear)
condition_ = sp_temp.sellCount > sheep_count_from_origin;
else
condition_ = sp_temp.sellCount >= sheep_count_from_origin;
if(condition_)
{
temp_sell_index[i-1]--;
break;
}
else
{
int income_from_origin = sp_temp.sellCount*sheepCost[i]+
sell_ordder[i-1][k].sellCount*sheepCost[i-1];
int income_from_remained = 0;
if(isLastYear)
condition_ = sp_temp.sellCount <= sheep_count_from_remaind;
else
condition_ = sp_temp.sellCount < sheep_count_from_remaind;
if(condition_)
{
income_from_remained = sp_temp.sellCount*sheepCost[i]+
sell_ordder[i-1][k].income;
}
if(income_from_origin > income_from_remained)
{
if(income_from_origin > sp_temp.income)
{
sp_temp.income = income_from_origin;
sp_temp.remained_from_pre_stage = sheep_count_from_origin;
}
if(sp_temp.income > maxForEachYear[i])
{
solution_sell_index[i] = j;
solution_sell_index[i-1] = k;
maxForEachYear[i] = sp_temp.income;
}
}
else
{
if(income_from_remained > sp_temp.income)
{
sp_temp.income = income_from_remained;
sp_temp.remained_from_pre_stage = sheep_count_from_remaind;
}
if(sp_temp.income > maxForEachYear[i])
{
solution_sell_index[i] = j;
solution_sell_index[i-1] = k;
maxForEachYear[i] = sp_temp.income;
}
}
}
}
sell_ordder[i][j] = sp_temp;
if(isLastYear)
j+=2;
else
j++;
}
if(isLastYear)
{
SheepSell sp_temp;
sp_temp.sellCount = sheepCountForEachYear[i];
sp_temp.remained_from_pre_stage = sheepCountForEachYear[i];
sp_temp.income = sheepCountForEachYear[i]*sheepCost[i];
if(sp_temp.income > maxForEachYear[i])
{
std::cout << "total income : " << sp_temp.income << "$\n";
std::cout << "kepp all sheeps and sell all of them at last year.\n";
}
else
{
std::cout << "total income : " << maxForEachYear[i] << "$\n";
for(int i=0;i<years;i++)
{
std::cout << "at year " << (i+1) << " sell " <<
sell_ordder[i][solution_sell_index[i]].sellCount << " sheeps.\n";
}
}
}
}
delete temp_sell_index;
delete solution_sell_index;
delete sheepCountForEachYear;
delete maxForEachYear;
for(int i=0;i<years;i++)
delete sell_ordder[i];
}
int main()
{
int *costs=0;
int years=0;
int initCount=0;
std::cout << "How Many Years ? ";
std::cin >> years;
std::cout << "How Many Sheeps ? ";
std::cin >> initCount;
std::cout << "\n";
costs = new int[years];
for(int i=0;i<years;i++)
{
std::cout << "Sheep cost at year " << (i+1) << " ? ";
std::cin >> costs[i];
}
dynamicSolve(years,initCount,costs);
getch();
return 0;
}
#include <iostream>
#include <vector>
struct DevelopingPlan
{
int income_from_plan;
int required_budget_for_plan;
};
struct DevelopngIncome
{
int income_without_developing;
int income_with_developint;
int remained_budget_without_developing;
int remained_budget_with_developing;
int index_max;
};
int main()
{
int factory_count,total_budget;
std::vector<int> developing_plane_count;
std::vector<std::vector<DevelopingPlan> *> Developing_plans;
std::vector<std::vector<DevelopngIncome> *> developing_incoms;
std::cout << "How many factories for developing ? ";
std::cin >> factory_count;
std::cout << "How much is total budget ? ";
std::cin >> total_budget;
for(int i=0;i<factory_count;i++)
{
Developing_plans.push_back(new std::vector<DevelopingPlan> );
developing_incoms.push_back(new std::vector<DevelopngIncome> );
}
for(int i=0;i<factory_count;i++)
{
int devel_plans;
std::cout << "How many developing plans has factory #" << (i+1) << " ? ";
std::cin >>devel_plans;
developing_plane_count.push_back(devel_plans);
for(int j=0;j<devel_plans;j++)
{
DevelopingPlan plan_;
std::cout << "How much budget does require plane#" << (j+1) << " from factory #" << (i+1) << " ? ";
std::cin >> plan_.required_budget_for_plan;
std::cout << "How much is income from plane#" << (j+1) << " from factory #" << (i+1) << " ? ";
std::cin >> plan_.income_from_plan;
Developing_plans[i]->push_back(plan_);
}
}
/*std::cout << "total budget : " << total_budget << "\n";
std::cout << "factory count : " << factory_count << "\n";
for(int i=0;i<factory_count;i++)
{
std::cout << "factory #" << (i+1) << " has " << developing_plane_count[i] << " developing plans\n";
for(int j=0;j<developing_plane_count[i];j++)
{
std::cout << " required budget of plane #" << (j+1) << " of factory #" << (i+1) << " : \n";
std::cout << Developing_plans[i]->at(j).required_budget_for_plan << " "
<< Developing_plans[i]->at(j).income_from_plan << "\n";
}
}*/
for(int i=0;i<developing_plane_count[0];i++)
{
DevelopngIncome vi;
vi.income_without_developing = 0;
vi.remained_budget_without_developing = total_budget;
vi.index_max = 0;
if(Developing_plans[0]->at(i).required_budget_for_plan < total_budget)
{
vi.income_with_developint = Developing_plans[0]->at(i).income_from_plan;
vi.remained_budget_with_developing = total_budget- Developing_plans[0]->at(i).required_budget_for_plan;
}
else
{
vi.income_with_developint = 0;
vi.remained_budget_with_developing = 0;
}
developing_incoms[0]->push_back(vi);
}
for(int i=1;i<factory_count;i++)
{
for(int j=0;j<developing_plane_count[i];j++)
{
DevelopngIncome di;
di.income_without_developing = 0;
di.income_with_developint = 0;
di.remained_budget_without_developing = 0;
di.remained_budget_with_developing = 0;
di.index_max = 0;
int current_income = Developing_plans[i]->at(j).income_from_plan;
int current_required = Developing_plans[i]->at(j).required_budget_for_plan;
for(int k=0;k<developing_plane_count[i-1];k++)
{
int remain_from_last_stag_with_devel =
developing_incoms[i-1]->at(k).remained_budget_with_developing;
int remain_from_last_stag_without_devel =
developing_incoms[i-1]->at(k).remained_budget_without_developing;
int income_from_last_stage_with_devel =
developing_incoms[i-1]->at(k).income_with_developint;
int income_from_last_stage_without_devel =
developing_incoms[i-1]->at(k).income_without_developing;
if(current_required < remain_from_last_stag_with_devel)
{
if(income_from_last_stage_with_devel+current_incom e > di.income_with_developint)
{
di.income_without_developing = income_from_last_stage_with_devel+current_income;
di.remained_budget_with_developing = remain_from_last_stag_with_devel-current_required;
di.index_max = k;
}
if(income_from_last_stage_with_devel > di.income_without_developing)
{
di.income_without_developing = income_from_last_stage_with_devel;
di.remained_budget_without_developing = remain_from_last_stag_with_devel;
di.index_max = k;
}
}
if(current_required < remain_from_last_stag_without_devel)
{
if(income_from_last_stage_without_devel+current_in come > di.income_with_developint)
{
di.income_without_developing = income_from_last_stage_without_devel+current_incom e;
di.remained_budget_with_developing = remain_from_last_stag_without_devel-current_required;
di.index_max = k;
}
if(income_from_last_stage_without_devel > di.income_without_developing)
{
di.income_without_developing = income_from_last_stage_without_devel;
di.remained_budget_without_developing = remain_from_last_stag_without_devel;
di.index_max = k;
}
}
}
developing_incoms[i]->push_back(di);
}
}
int max_income = 0;
for(int i=0;i<developing_plane_count[factory_count-1];i++)
{
if(max_income < developing_incoms[factory_count-1]->at(i).income_with_developint)
max_income = developing_incoms[factory_count-1]->at(i).income_with_developint;
if(max_income < developing_incoms[factory_count-1]->at(i).income_without_developing)
max_income = developing_incoms[factory_count-1]->at(i).income_without_developing;
}
std::cout << max_income;
return 0;
}
پاسخ با نقل قول
نوشته شده توسط rezaricky
