用动态规划、分支限界、回溯解决01背包、批处理作业调度问题

用动态规划、分支限界、回溯解决01背包、批处理作业调度问题

#include
#include
using namespace std;
typedef struct treenode{
	int weight;
	int value;
	int level;
	int flag;
}treenode;
queue que;
int enQueue（int w int v int level int flag int n int* bestvalue）
{
	treenode node;
	node.weight = w;
	node.value = v;
	node.level = level;
	node.flag = flag;
	if （level == n）
	{
		if （node.value > *bestvalue）
		{
			*bestvalue = node.value;
		}
		return 0;
	}
	else
	{
		que.push（node）;
	}
}
//w为重量数组，v为价值数组，n为物品个数，c为背包容量，bestValue为全局最大价值
int bbfifoknap（int w[] int v[] int n int c int* bestValue）
{
	//初始化结点
	int i = 1;
	treenode tag livenode;
	livenode.weight = 0;
	livenode.value = 0;
	livenode.level = 1;
	livenode.flag = 0;//初始为0
	tag.weight = -1;
	tag.value = 0;
	tag.level = 0;
	tag.flag = 0;//初始为0
	que.push（tag）;
	while （1）
	{
		if （livenode.weight + w[i - 1] <= c）
		{
			enQueue（livenode.weight + w[i - 1] livenode.value + v[i - 1] i 1 n bestValue）;
		}
		enQueue（livenode.weight livenode.value i 0 n bestValue）;
		livenode = que.front（）;
		que.pop（）;
		if （livenode.weight == -1）
		{
			if （que.empty（） == 1）
			{
				break;
			}
			livenode = que.front（）;
			que.pop（）;
			que.push（tag）;
			i++;
		}

	}
	return 0;
}
void test_bbfifoknap（）
{
	int w[] = { 16 15 15 };
	int v[] = { 45 25 25 };
	int n = 3;
	int c = 30;
	int bestValue = 0;
	bbfifoknap（w v n c &bestValue）;
	printf（“weight[3]= { 16 15 15 };\n“）;
	printf（“value[3] = { 45 25 25 };\n“）;
	printf（“c=30;\n“）;
	cout << “result = “<< bestValue << endl;

}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       1649  2018-03-01 16:08  Algorithm\Algorithm\01_分支限界.cpp

     文件        957  2018-03-01 16:09  Algorithm\Algorithm\01_动态规划.cpp

     文件        807  2018-03-01 16:08  Algorithm\Algorithm\01_回溯法.cpp

     文件       4393  2018-01-17 23:15  Algorithm\Algorithm\Algorithm.vcxproj

     文件       1552  2018-01-17 23:15  Algorithm\Algorithm\Algorithm.vcxproj.filters

     文件     243027  2018-03-01 16:08  Algorithm\Algorithm\Debug\01_分支限界.obj

     文件     136173  2018-03-01 20:21  Algorithm\Algorithm\Debug\01_动态规划.obj

     文件     136234  2018-03-01 16:08  Algorithm\Algorithm\Debug\01_回溯法.obj

     文件        606  2018-01-17 23:16  Algorithm\Algorithm\Debug\Algorithm.Build.CppClean.log

     文件        765  2018-03-30 17:38  Algorithm\Algorithm\Debug\Algorithm.log

     文件        157  2018-03-30 17:38  Algorithm\Algorithm\Debug\Algorithm.tlog\Algorithm.lastbuildstate

     文件       3702  2018-03-30 17:38  Algorithm\Algorithm\Debug\Algorithm.tlog\cl.command.1.tlog

     文件      52778  2018-03-30 17:38  Algorithm\Algorithm\Debug\Algorithm.tlog\CL.read.1.tlog

     文件       5568  2018-03-30 17:38  Algorithm\Algorithm\Debug\Algorithm.tlog\CL.write.1.tlog

     文件       1780  2018-03-01 20:21  Algorithm\Algorithm\Debug\Algorithm.tlog\link.command.1.tlog

     文件       3458  2018-03-01 20:21  Algorithm\Algorithm\Debug\Algorithm.tlog\link.read.1.tlog

     文件        896  2018-03-01 20:21  Algorithm\Algorithm\Debug\Algorithm.tlog\link.write.1.tlog

     文件          0  2018-03-30 17:38  Algorithm\Algorithm\Debug\Algorithm.tlog\unsuccessfulbuild

     文件     168361  2018-03-01 15:34  Algorithm\Algorithm\Debug\mask_分支限界.obj

     文件     157850  2018-03-01 16:04  Algorithm\Algorithm\Debug\mask_回溯.obj

     文件     379904  2018-03-30 17:38  Algorithm\Algorithm\Debug\vc120.idb

     文件     389120  2018-03-30 17:38  Algorithm\Algorithm\Debug\vc120.pdb

     文件       2252  2018-01-17 23:15  Algorithm\Algorithm\head.h

     文件        615  2018-03-30 17:38  Algorithm\Algorithm\main.cpp

     文件       4850  2018-01-17 23:18  Algorithm\Algorithm\mask_分支限界.cpp

     文件       1323  2018-03-01 16:04  Algorithm\Algorithm\mask_回溯.cpp

     文件    8454144  2018-03-30 17:39  Algorithm\Algorithm.sdf

     文件        973  2018-01-17 22:26  Algorithm\Algorithm.sln

    ..A..H.     29696  2018-03-30 17:39  Algorithm\Algorithm.v12.suo

     文件     100352  2018-03-01 20:21  Algorithm\Debug\Algorithm.exe

............此处省略10个文件信息