旅行の售货员
//售货员の周游路线 P122
//从1出发，各点走一遍后回到起点
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define maxx 0x3f3f3f
int c, e; //【城市个数】【道路数量】
int w1[100], way1; //当前路径 当前总路程
int w2[100], best; //最佳路径 最小总路程
int G[100][100]; //图【出发点】【目标点】
void init()
{
way1 = 0;
best = maxx;
for (int k = 1; k <= c; k++)
w1[k] = k;
}
void get()
{
int p1, p2, l; //点1 点2 距离
printf("输入【城市数】【道路数】：\n");
scanf("%d%d", &c, &e);
memset(G, -1, sizeof(G));
printf("道路情况部署【P1 P2 Len】：\n");
for (int k = 1; k <= e; ++k)
{
scanf("%d%d%d", &p1, &p2, &l);
G[p1][p2] = G[p2][p1] = l;
}
init();
}
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
void ans()
{
printf("Min_Way=%d\n", best);
printf("Way_Back：");
for (int x = 1; x <= c; x++)
printf("%d ", w2[x]);
printf("1\n");
}
bool pd1() //【更小的总路程】
{
if (G[w1[c - 1]][w1[c]] != -1 && G[w1[c]][w1[1]] != -1 && (way1 + G[w1[c - 1]][w1[c]] + G[w1[c]][w1[1]] < best || best == maxx))
return true; //到叶路 叶归路 存在 且相加更优化
else //或者best还没更新过（防止相加后还比max大）
return false;
}
bool pd2(int k, int y)
{
if (G[w1[k - 1]][w1[y]] != -1 && (way1 + G[w1[k - 1]][w1[y]] < best || best == maxx))
return true; //到y点有路 当前局部比较优秀（剪枝）或 还没启动过
else
return false;
}
void Find_way(int k) // i迭代深度
{
if (k == c && pd1()) //若：探测到底，且为最小距离
{ //【最小距离】=当前距离+到叶距离+叶归距离
// k-1是因为递归指针刚来，走来位置k的距离还没算
best = way1 + G[w1[k - 1]][w1[k]] + G[w1[k]][w1[1]];
for (int x = 1; x <= c; x++) //保存路径
w2[x] = w1[x];
}
else // 还没探测到底，继续探测
{
for (int y = k; y <= c; y++) //【交换】当前点和此点之后的点（全排列）
{
if (pd2(k, y)) //剪枝判断
{ // k是【基准点】，y是【试图交换点】
swap(w1[k], w1[y]);
way1 += G[w1[k - 1]][w1[k]]; //探测，对【试图交换点】（已易位到基准点）
Find_way(k + 1); //递归
way1 -= G[w1[k - 1]][w1[k]]; //回溯
swap(w1[k], w1[y]);
}
}
}
}
int main()
{
get();
init();
Find_way(2);
ans();
return 0;
}
/*
4 6
1 2 30
1 3 6
1 4 4
2 4 10
2 3 5
3 4 20
*/
装载问题
//【5.2装载问题】
#include <iostream>
#include <stdio.h>
using namespace std;
int n, w[274], c1, c2;
int now, best;
bool way1[274], way2[274]; //当前路径，最佳路径
void init()
{
printf("输入【两船载货容量】:");
scanf("%d%d", &c1, &c2);
printf("输入【集装箱个数】：");
scanf("%d", &n);
for (int x = 1; x <= n; x++)
scanf("%d", &w[x]);
now = best = 0;
for (int x = 0; x <= n; x++)
way1[x] = false;
}
void work(int k)
{
if (k > n) //此时溢出，说明n个选择情况都已完成
{
if (now > best)
{
best = now;
for (int x = 1; x <= n; x++)
way2[x] = way1[x];
}
return;
}
if (now + w[k] <= c1) // C1船还放得下
{
//【装一下玩玩】
now += w[k];
way1[k] = true;
work(k + 1);
//【回溯拿出来】就当啥也没发生过
now -= w[k];
way1[k] = false;
}
// C1能放，但是我就是不放第k个，直接往下探索
work(k + 1);
}
void ans()
{
int sum = 0;
printf("货船1号最大载货量=%d\t集装箱编号：", best);
for (int x = 1; x <= n; x++)
{
if (way2[x])
printf("%d ", x);
else
sum += w[x];
}
printf("\n剩余集装箱总重：%d\t", sum);
if (sum > c2)
printf("大于货船2号载重总量%d\n任务失败！", c2);
else if (sum < c2)
printf("小于货船2号载重总量%d\n任务成功！", c2);
else
printf("恰好等于货船2号载重总量%d\n有惊无险！", c2);
}
int main()
{
init();
work(1);
ans();
return 0;
}
/*
50 50
3 10 40 40
50 50
3 20 40 40
*/
批处理作业调度
//【批处理作业调度】
#include <stdio.h>
#include <iostream>
#define maxx 0xfffffff
using namespace std;
int n, m[274][2]; //【作业总数】【批改所需用时】0是T1机，1是T2机
int f, bestf; //【当前·总时间】【最优·总时间】
int f1, f2; //【机器1·完成工作の时间戳】【机器2·完成工作の时间戳】
//由于T2机器会受到T1机器工作进度の影响，需要存储之前的工作情况
int way1[274], way2[274]; //【当前路径】【最佳路径】
void ans();
void init() //《数据输入》
{
printf("输入【作业总数】：");
scanf("%d", &n);
for (int x = 1; x <= n; x++)
scanf("%d%d", &m[x][0], &m[x][1]);
// 0是 T1用时 1是T2用时
f = f1 = f2 = 0;
bestf = 274540;
for (int x = 1; x <= n; x++)
way1[x] = x; //注意！这里要初始化！！缺失这里会导致异常
}
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
void work(int k) //《回溯·剪枝》 部署·第k个位置
{
if (k > n) //完成所有部署
{
if (f < bestf) //更优秀的结果
{
// printf("巧喑最可爱！");
bestf = f;
for (int x = 1; x <= n; x++)
way2[x] = way1[x];
}
return;
}
else
{
for (int x = k; x <= n; x++) //【交换·全排列】·与·后续所有数字尝试交换
{
int t = f2; //【F2先锋时间】
f1 += m[way1[x]][0]; //【机器T1·完成作业批改】后的时间戳
f2 = (f2 > f1 ? f2 : f1) + m[way1[x]][1]; //【机器T2·完成作业批改】后の时间戳
f += f2; //【当前作业T2完成实践】
//由【之前工作完成の时间点】+【当前作业批改所需用时】
//受到【机器T1】【前项任务进度】的影响，取最大值
//要么，机器T1还没改完，还不能开始工作
//要么，机器T2还没改完之前的作业，暂时不能响应当前的工作请求
if (f < bestf) //【剪枝】局部如果不够优秀，直接舍弃，不探索子树情况
{
swap(way1[k], way1[x]);
work(k + 1);
swap(way1[k], way1[x]);
}
f -= f2; //【当前作业T2完成时间】
f2 = t; //重要！还原f2为先锋时间
f1 -= m[way1[x]][0];
}
}
}
void ans() //《答案汇报》
{
printf("min_time=%d\n", bestf);
printf("Way：");
for (int x = 1; x <= n; x++)
printf("%d ", way2[x]);
printf("\n");
}
int main()
{
init();
work(1);
ans();
return 0;
}
/*
3
2 1
3 1
2 3
*/
|