PDL学习
PDL (Problem Description Language)是一种用于组合优化问题建模的语言。
简答测评？用户体验（雾
大体感觉主要用于搜索问题的求解，模拟了人的思考模式，将需求和限定写出，可以由简单几行代码实现需求，自动生成可行的求解算法及相应的源代码
可以发现其对于算法匹配较为精准，复杂度较低，但难以做到最优复杂度，且目前来看比较容易实现较简单的算法，而更高级的算法或嵌套难以实现或表达，仍有很大上升空间
可能因为PDL和常规算法对于问题实现思路不一致，初次接触上手较难，但熟悉之后，应该会对部分搜索问题的实现起到很大的帮助，或许将会极大的减小代码实现的难度和代码工程量
A:找相同数
总时间限制: 1000ms 内存限制: 65536kB
描述
在长度为n（1<=n<=1000）的整数（每个整数在0~10000之间）序列中，找到出现了两次的数。
输入
第一行输入一个整数n
第二行输入序列，用空格分开
输出
出现了两次的数，保证存在且唯一
样例输入
4 1 2 4 2
样例输出
2
我们可以发现常规做法可能重在储存信息来减小复杂度
而PDL则基于的是搜索的思想
#input
N of int in [1,1000];
a of (int in [0,10000]) [1~N];
#required
i of int in [1,N];
j of int in [1,N];
a[i]=a[j] and i<j;
#output
a[i];B:旅行商问题
总时间限制: 1000ms 内存限制: 65536kB
描述
某国家有n（1<=n<=10）座城市，给定任意两座城市间距离（不超过1000的非负整数）。一个旅行商人希望访问每座城市恰好一次（出发地任选，且最终无需返回出发地）。求最短的路径长度。
输入
第一行输入一个整数n
接下来n行，每行n个数，用空格隔开，以邻接矩阵形式给出城市间距离。该邻接矩阵是对称的，且对角线上全为0
输出
一行，最短路径的长度
样例输入
6 0 16 1 10 12 15 16 0 10 2 10 8 1 10 0 10 5 10 10 2 10 0 9 3 12 10 5 9 0 8 15 8 10 3 8 0
样例输出
19
#input
n of int in [1,10];
lj of (int in [0 ,1000])[1~n][1~n];
#required
a of (int in[1,n])[1~n];
alldiff a;
#objective
minimize summation [lj[a[i]][a[i+1]] : forall i (i of int in [1,n-1])];C:团队合作
总时间限制: 1000ms 内存限制: 65536kB
描述
你需要挑选若干成员组建一个工作团队。现有n（1<=n<=100）名候选人，每个人有一个“凝聚力”和一个“工作能力”（均为-50至50的整数）。要确保团队能够顺利合作，所有成员的“凝聚力”之和必须为正。在这个条件下，团队的总“工作能力”最大是多少？保证至少存在一个满足条件且总“工作能力”为正的团队。
输入
第一行输入一个整数n
第二行输入n个整数，用空格隔开，依次为各候选人的凝聚力
第三行输入n个整数，用空格隔开，依次为各候选人的工作能力
输出
一个整数，最大的团队总“工作能力”
样例输入
5 -5 8 6 2 -8 7 -6 -3 1 -5
样例输出
5
#input
n of int in [1,100];
a of (int in [-50,50])[1~n];
b of (int in [-50,50])[1~n];
#required
ans of (int in [1,n]) {};
summation [a[i] : forall i (i in ans)]>0;
#objective
maximize summation [b[i] : forall i (i in ans)];PDL2CPP Source Code
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<set>
int n;
int a[100];
int b[100];
int ans[100];
int _result;
int _best__result;
void _input() {
std::cin >> n;
for (int _tmp0 = 1; _tmp0 <= n; _tmp0++)
std::cin >> a[_tmp0 - 1];
for (int _tmp0 = 1; _tmp0 <= n; _tmp0++)
std::cin >> b[_tmp0 - 1];
}
void _output() {
std::cout << _best__result << std::endl;
}
void _update() {
if (_result <= _best__result)
return;
_best__result = _result;
}
int _DP_ans[100][5001];
int _find_ans(int _step, int _sum1, int _sum2) {
if (_step == n - 1 + 1) {
_result = _sum2;
if (!(_sum1 > 0))
return -5001;
_update();
return _sum2;
}
if (_DP_ans[_step][_sum1] != -5001) {
_sum2 += _DP_ans[_step][_sum1];
_result = _sum2;
if (!(_sum1 > 0))
return -5001;
_update();
return _sum2;
}
int __sum1 = _sum1;
int __sum2 = _sum2;
for (ans[_step] = 0; ans[_step] <= 1; ans[_step]++) {
_sum1 = __sum1;
_sum2 = __sum2;
if (ans[_step + 1 - 1])
_sum1 += a[_step + 1 - 1];
if (ans[_step + 1 - 1])
_sum2 += b[_step + 1 - 1];
if (!(_sum1 + 50 * (100 - _step) > 0))
continue;
if (!(_sum2 + 50 * (100 - _step) > _best__result))
continue;
int _tmp0 = _find_ans(_step + 1, _sum1, _sum2) - __sum2;
if (_tmp0 > _DP_ans[_step][__sum1])
_DP_ans[_step][__sum1] = _tmp0;
}
return __sum2 + _DP_ans[_step][__sum1];
}
void _solve() {
_best__result = -5001;
for (int _tmp0 = 0; _tmp0 < 100; _tmp0++)
for (int _tmp1 = 0; _tmp1 < 5001; _tmp1++)
_DP_ans[_tmp0][_tmp1] = -5001;
_find_ans(0, 0, 0);
}
int main() {
_input();
_solve();
_output();
return 0;
}
发表评论