brach and bound for subset sum

只是解决  profit =weight的情况

// C++ program to solve knapsack problem using
// branch and bound
//#include// C++ program to solve knapsack problem using
// branch and bound
//#include <bits/stdc++.h>
#include<algorithm>
#include<deque>
#include <queue>
#include <iostream>
#include<fstream>
#include<string>
#include<iomanip>
using namespace std;

// Structure for Item which store weight and corresponding
// value of Item

vector<float> weights; //一维数组存储读入变量 数据下标从1开始
vector<int> bestx; // 用来存放x的解 数据下标从1开始

int total = 1; // 记录搜索树的的节点的标号
int n; // 物品的个数为 n-1, 而不是 n
// vector中无法访问 weights[n] 元素。
float incumbent = 0;
float capacity;

// Node structure to store information of decision
// tree
struct Node
{
int no; // 节点编号
// level --> Level of node in decision tree (or index
// in arr[]
// profit --> Profit of nodes on path from root to this
// node (including this node)
// bound ---> Upper bound of maximum profit in subtree
// of this node/
int level;
float profit, bound, weight;
vector <int> current_x;
bool operator < (const Node& s) const
{
return bound < s.bound;
}
};

struct soltion {
float value;
vector <int> x;
};
vector <soltion> all_solutions;

// driver program to test above function

inline void file_to_string(vector<string>& record, const string& line, char delimiter);
inline float string_to_float(string str);
inline void file_to_string(vector<string>& record, const string& line, char delimiter)
{
int linepos = 0;
char c;
int linemax = line.length();
string curstring;
record.clear();
while (linepos < linemax)
{
c = line[linepos];
if (isdigit(c) || c == '.') {
curstring += c;
}
else if (c == delimiter && curstring.size()) {
record.push_back(curstring);
curstring = "";
}
++linepos;
}
if (curstring.size())
record.push_back(curstring);
return;
}

inline float string_to_float(string str) {
int i = 0, len = str.length();
float sum = 0;
while (i < len) {
if (str[i] == '.') break;
sum = sum * 10 + str[i] - '0';
++i;
}
++i;
float t = 1, d = 1;
while (i < len) {
d *= 0.1;
t = str[i] - '0';
sum += t * d;
++i;
}
return sum;
}

//
//https://www.cnblogs.com/exciting/p/11015115.html

void read()
{
vector<string> row;
string line;
string filename;
ifstream in("test.csv");
if (in.fail()) { cout << "File not found" << endl; return; }

getline(in, line);
while (getline(in, line) && in.good())
{
file_to_string(row, line, ','); //把line里的单元格数字字符提取出来，“,”为单元格分隔符
//这里只取第二个数字
/* for (int i = 0, leng = row.size(); i < leng; i++) {

loop_temp.push_back(string_to_float(row[i]));

}*/
weights.push_back(string_to_float(row[1]));
}
in.close();
return;
}

void bound(Node& curr_node)
{
float sumw = curr_node.weight;

int i = curr_node.level + 1;
if (i == n) cout<< "bound: out of range" << endl;
//float sumv = curr_node.profit;
while (i < n &&(sumw + weights[i] <= capacity) )
{
sumw += weights[i];
i++;
}
if (i < n) curr_node.bound = capacity;
else curr_node.bound = sumw;
}

void EnQueue(Node curr_node, priority_queue <Node>& qu)
{
if (curr_node.level == n-1)
{
if (curr_node.weight > incumbent)
{
incumbent = curr_node.weight;
bestx = curr_node.current_x;
soltion curr_sol;
curr_sol.value= incumbent;
curr_sol.x = bestx;
all_solutions.push_back(curr_sol);
}
}
else qu.push(curr_node);
}

void bfs()
{
int j;
Node curr, curr_l, curr_r;
priority_queue <Node> qu;
curr.level = 0;
curr.weight = curr.profit = 0;
curr.no = total++;
for (j = 0; j < n; j++)
curr.current_x.push_back(0);
bound(curr);
qu.push(curr);
while (!qu.empty())
{
curr = qu.top(); qu.pop();
// if (curr.level + 1 == n) cout << "bfs: out of range" << endl;
if (curr.weight + weights[curr.level + 1] <= capacity)
{
curr_l.no = total++;
curr_l.level = curr.level + 1;
curr_l.weight = curr.weight + weights[curr_l.level];
curr_l.current_x = curr.current_x;
curr_l.current_x[curr_l.level] = 1;
if (curr_l.level < n-1) bound(curr_l);
EnQueue(curr_l,qu);
}
curr_r.no = total++;
curr_r.level = curr.level + 1;
//if (curr.level + 1 == n) cout << "bfs: out of range" << endl;
curr_r.weight = curr.weight;
curr_r.current_x = curr.current_x;
curr_r.current_x[curr_r.level] = 0;
if (curr_r.level < n - 1) bound(curr_r);
if (curr_r.bound > incumbent) EnQueue(curr_r, qu);
}
}

int main()
{
capacity = 3353000; // Weight of knapsack

//数据下标从1开始
weights.push_back(0);
read();

n = weights.size();
cout << n << endl;

clock_t start, end;
start = clock();
bfs();
end = clock();
cout << incumbent << endl;
cout << "The running time is " << double(end - start) / CLOCKS_PER_SEC << "s" << endl;
cout << "total number of nodes visited is " << total << endl;

float sum_temp = 0;
for (int i = 1; i < n; i++)
{
if (bestx[i] == 1)
{
cout << "(" << i << "," << weights[i] << ")"<< endl;
sum_temp += weights[i];
}
}
cout << setprecision(10) << sum_temp << endl;

//for (int i = 0; i < all_solutions.size(); i++)
// cout << all_solutions[i].value << endl;

system("pause");
return 0;
}