#include "Method.h"
#ifdef BackTrack
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct object //物品定义
{
float weight; //重量
float value; //价值
};
float capacity; //背包容量
int amount; //物品数量
object* objects; //物品
float maxValue; //最大价值
bool* bestResult; //最优解
bool* tempResult; //临时解
void backTrack(int level, float weight, float value)
{
//在树的底层，保存结果，并终结
if(level == amount)
{
if(value > maxValue)
{
maxValue = value;
memcpy(bestResult, tempResult, amount);
}
return;
}
//不放当前物品，继续回溯
tempResult[level] = false;
backTrack(level + 1, weight, value);
//仅在有必要时放当前物品，继续回溯
float curWeight = weight + objects[level].weight;
if(curWeight <= capacity)
{
tempResult[level] = true;
backTrack(level + 1, curWeight, value + objects[level].value);
}
}
bool sortObjects(object& obj1, object& obj2)
{
//按单位价值排序
return obj1.value/obj1.weight > obj2.value/obj2.weight;
}
int main()
{
//输入数据
cout << "当前方式：回溯法解01背包问题\n\n";
cout << "输入背包容量 : "; cin >> capacity;
cout << "输入物品数量 : "; cin >> amount;
objects = new object[amount];
cout << "输入 " << amount << " 个物品的重量和价值\n";
for(int i=0; i<amount; i++)
{
cout << i + 1 << " : ";
cin >> objects[i].weight >> objects[i].value;
}
//排序并计算
maxValue = 0;
bestResult = new bool[amount];
fill(bestResult, bestResult + amount, false);
tempResult = new bool[amount];
fill(tempResult, tempResult + amount, false);
sort(objects, objects + amount, sortObjects);
backTrack(0, 0, 0);
//输出结果
cout << "计算结果(物品已排序) : 最大价值=" << maxValue << endl;
for(int i=0; i<amount; i++)
{
cout << "物品=" << left <<setw(3) << i + 1;
cout << " 重量=" << left << setw(3) << objects[i].weight;
cout << " 价值=" << left << setw(3) << objects[i].value;
cout << (bestResult[i] ? " 结果=1":" 结果=0") << endl;
}
//释放内存
delete[] objects, bestResult, tempResult;
system("pause");
}
#endif
