代码拉取完成,页面将自动刷新
#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef struct
{
int s; //始发站号
int t; //终点站号
int pop; //
} Order;
int m, n, nOrder;
vector<Order> orders; //大小为o,储存全部订单
vector<int> status; //大小为o, 储存订单的选择情况
vector<int> maxStatus; //大小为o, 储存最大收入订单的选择情况
vector<int> client; //大小为m, 储存每一站的乘客数量
int income = 0;
int maxIncome = 0;
int maxClient() //计算这一订单同时在车上的最大乘客人数
{
int max = client[0];
for (int i=1; i<m; i++)
if(client[i] > max)
max = client[i];
return max;
}
void BinaryEnumeration()
{
for(int k = 0; k < (1<<nOrder); k++) //遍历所有可能的情况
{
income = 0;
for(int i=0; i < nOrder; i++)
{
client[i] = 0;
}
for(int j = 0; j < nOrder; j++)
{
if(k & (1 << j)) //选择第j个订单的情况,即i的第j位是不是1
{
for (int i=orders[j].s; i<orders[j].t; i++) //加上第j个订单的乘客人数
client[i] = client[i] + orders[i].pop;
if (maxClient() <= n) //检验,当该订单能装下乘客数量时,说明可以选择该订单
{
status[j] = 1;
income = income + orders[j].pop * (orders[j].t-orders[j].s); //加上第j个订单的收入
if (j == nOrder-1) //到达订单列表底部,即有一种选择方案的时候,更新最大收入情况
{
if (income > maxIncome) //更新最大收入
{
maxStatus = status;
maxIncome = income;
}
}
}
else //该订单不能装下乘客数量时
{
for (int i=orders[j].s; i<orders[j].t; i++) //减去第p个订单的乘客人数
client[i] = client[i]-orders[i].pop;
status[j] = 0;
}
} //if(i&(1<<j))
else //不选择第j个订单的时候
{
status[j] = 0;
if (j == nOrder-1) //到达订单列表底部,即有一种选择方案的时候,更新最大收入情况
{
if (income > maxIncome) //更新最大收入
{
maxStatus = status;
maxIncome = income;
}
}
}
}
//输出第k种情况下的收入值
cout << k << ":" << income << endl;
}
}
int main()
{
cin >> n >> m >> nOrder;
orders.resize(nOrder); // 此处必须resize动态调整数组大小,否则会报错variable-sized object may not be initialized
status.resize(nOrder);
client.resize(m);
for (int i=0; i<nOrder; i++)
cin >> orders[i].s >> orders[i].t >> orders[i].pop;
for (int i=0; i<m; i++) //初始化乘客人数
client[i] = 0;
//search(0);
BinaryEnumeration();
cout << "Maximum income = " << maxIncome << endl;
cout << "Choose these order:" << endl;
for (int i=0; i<nOrder; i++)
if(maxStatus[i])
cout << i+1 << ' ';
cout << endl;
return 0;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。