c++木材加工问题
工厂准备使用机器加工一批木材。每根木材有两
个参数l 和w，即木材的长度和木材的重量。由于只有一
台机器，所以木材只能一次加工一根。在加工每根机器
前，需要设置一下机 器，这需要花费一定的时间，我们
称为设置时间。设置时间可以按如下方法计算：
（1）机器加工第一根木材时，需要1分钟的设置时间；
（2）加工完一根木材（参数为l 和w）后，如果下一根要
加工的木材的参数l’与w’满足l<=l’与w<=w’，则不需要重
新设置即可加工，即设置时间为0；否则需要1分钟的设
置时间。
Input
输入数据第一行包含1 个整数N(1<=N<=5000)，表示要加工木材的数量。接下来有2*N个整数l1 w1 l2 w2……，表示每根木材的长度与重量。
Output
输出一个整数，表示加工完这批木材，至少需要多少分钟的加工时间。
[解决办法]
由于我的权值阵是个反对称阵，也即使若a[i][j] = 1,则a[j][i] = 0;因此，总能尽最大可能走值为0的结点且走到最大程度！（因为不一定是个连通图），那么剩余的结点插到已经生成的路径当中去时，就是导致每插入一个结点，对应时间加1！
我还不太保证我的做法正确，我正在尝试用数学证明一下它的正确性！先贴出来，抛砖引玉！
#include <iostream>
using namespace std;
class timber{
private:
int size;//尺寸
int mass;//质量
public:
timber()
{
this->size = 0;
this->mass = 0;
}
timber(int size, int mass) : size(size), mass(mass){};
~timber(){}
int cmp(timber *t_right);
//输入或者输出时候需要
void set_value(int size, int mass)
{
this->size = size;
this->mass = mass;
}
void get_value(int *size, int *mass)
{
*size = this->size;
*mass = this->mass;
}
};
int timber::cmp(timber *t_right)
{
//不需要设置时间
if (this->mass <= t_right->mass && this->size <= t_right->size)
{
return 0;
}
else//需要重新设置时间
return 1;
}
static int level = 0, min_time = 5001;
void compute(short **matrix, short *path, int n, int start)
{
++level;//递归调用的层数，就是经过的结点的个数
int i, j;
for (i = 0; i < n; ++i)
{
if (matrix[start][i] == 0)
{
//检测结点是否被访问过
for (j = 0; j < level; ++j)
{
if (path[j] == i)//被访问过
{
break;
}
}
if (j == level)//没有被访问
{
path[level] = i;//记录位置
compute(matrix, path, n, i);//以i为起点，继续深入递归
}
}
}//没有值为0的结点了
//输出路径
cout << "\nstart->";
for (i = 0; i < level; ++i)
{
cout << path[i] << " -> ";
}
cout << "end;" << "times: " << n - level + 1 << endl;
min_time = min_time > (n - level + 1) ? (n - level + 1) : min_time;
--level;
}
int main()
{
int i = 0, j;
int num;
cout << "N = ";
cin >> num;
//获取木材原数据
timber *source = new timber[num];
while(i != num)
{
int temp[2];
cin>>*temp>>*(temp + 1);
(source + i)->set_value(temp[0], temp[1]);
++i;
}
//生成权值阵
short *path = new short[num];
short **matrix = new short*[num];
for (i = 0; i < num; ++i)
{
matrix[i] = new short[num];
}
for (i = 0; i < num; ++i)
{
path[i] = -1;
matrix[i][i] = num + 1; //最大时间就是num，因此对角线上的权值稍大num即可表示无穷大
for (j = i + 1; j < num; ++j)
{
int temp = (source + i)->cmp(source + j);
matrix[i][j] = temp;
matrix[j][i] = (temp ? 0 : 1);
}
}
for (i = 0; i < num; ++i)
{
for (j = 0; j < num; ++j)
{
cout<< " " << matrix[i][j];
}
cout<<endl;
}
//不同起点
for (i = 0; i < num; ++i)
{
cout << "lev:" << level <<endl;
path[0] = i;
compute(matrix, path, num, i);
cout<<endl;
}
cout << "min time: " << min_time << endl;
//释放内存
delete []source;
for (i = 0; i < num; ++i)
{
delete [] matrix[i];
}
delete matrix;
delete []path;
return 0;
}
