最小重量問題の分岐限界法のC++実現案

*1.問題の説明:*
*2.解題構想*この問題の基本思想は分岐限界法を利用することであり、核心は優先度基準を設計する必要がある.ここでは問題の層数、すなわちi番目の部品を優先度とし、同じiの部品に対して、重量がより小さいことを優先度の評価基準とし、標準ライブラリの優先度キューを利用して実現する.分岐限界法でターゲットを検索します.
また、標準ライブラリの優先順位キューを使用する場合はoperator<を自分でリロードする必要があり、const,233333333が必要であることに注意してください.
3.ソース3.1 MinMachine.h

#pragma once
#include <queue>

typedef struct _Node 
{
    _Node * parent;
    int total_price;
    int total_weight;
    int priority;
    int supplier_id;

    _Node()
    {
        parent = nullptr;
        total_weight = 0;
        total_price = 0;
        priority = 0;
        supplier_id = 0;
    }


    //************************************
    // Method: operator<
    // FullName: _Node::operator<
    // Access: public 
    // Returns: bool
    // Qualifier: const
    // Parameter: const _Node & a
    //        ，    ，     
    //      ，         ，       
    //************************************
    bool operator< (const _Node & a) const
    {
        if (priority < a.priority)
            return true;

        if (priority == a.priority)
            if (total_weight <= a.total_weight)
                return true;

        return false;
    }

}Node;

class CMinMachine
{
public:
    CMinMachine();
    ~CMinMachine();

public:
    int solve();

private:
    void ReadFile();
    void WriteFile();
    void SearchRes();
    void output(Node * curNode);
    bool IsOK(int cur_price);

private:
    int m_m;
    int m_n;
    int m_d;
    int ** m_c;
    int ** m_w;

    std::priority_queue<Node> MachHeap;
    int m_best;
    int * m_select_best;
};

3.2.MinMachine.cpp

#include "MinMachine.h"
#include <fstream>

CMinMachine::CMinMachine()
{
    m_m = 0;
    m_n = 0;
    m_d = 0;
    m_c = NULL;
    m_w = NULL;

    m_best = 0;
    m_select_best = nullptr;
}


CMinMachine::~CMinMachine()
{
    for (int i = 0; i != m_n; i++)
    {
        if (m_c[i])
            delete m_c[i];

        if (m_w[i])
            delete m_w[i];
    }

    if (m_c)
        delete[] m_c;

    if (m_w)
        delete[] m_w;

    if (m_select_best)
        delete m_select_best;
}


void CMinMachine::ReadFile()
{
    std::ifstream infile("input.txt");
    infile >> m_n >> m_m >> m_d;

    m_c = new int *[m_n];
    m_w = new int *[m_n];
    for (int i = 0; i != m_n; i++)
    {
        m_c[i] = new int[m_n];
        m_w[i] = new int[m_n];

        memset(m_c[i], 0, sizeof(m_c[i]));
        memset(m_w[i], 0, sizeof(m_w[i]));

        for (int j = 0; j != m_n; j++)
        {
            infile >> m_c[i][j];
        }
    }

    for (int i = 0; i != m_n; i++)
    {
        for (int j = 0; j != m_n; j++)
        {
            infile >> m_w[i][j];
        }
    }

    m_select_best = new int[m_n];
    memset(m_select_best, 0, sizeof(m_select_best));
}

void CMinMachine::WriteFile()
{
    std::ofstream outfile("output.txt");
    outfile << m_best << std::endl;
    for (int i = 0; i != m_n; i++)
    {
        outfile << m_select_best[i] + 1 << "\t";
    }
    outfile << std::endl;
}

int CMinMachine::solve()
{
    ReadFile();

    SearchRes();

    WriteFile();

    return m_best;
}

//************************************
// Method: SearchRes
// FullName: CMinMachine::SearchRes
// Access: private 
// Returns: void
// Qualifier:          ，                
//************************************
void CMinMachine::SearchRes()
{
    Node root;
    MachHeap.push(root);

    while (true)
    {
        Node * curNode = new Node(MachHeap.top());
        MachHeap.pop();

        if (curNode->priority == m_n - 1)
        {
            output(curNode);
            return;
        }

        for (int i = 0; i != m_m; i++)
        {
            Node * subNode = new Node;
            subNode->parent = curNode;
            subNode->total_price = curNode->total_price + m_c[curNode->priority][i];
            subNode->total_weight = curNode->total_weight + m_w[curNode->priority][i];
            subNode->priority = curNode->priority + 1;
            subNode->supplier_id = i;

            if (IsOK(subNode->total_price))
                MachHeap.push(*subNode);
        }
    }
}

void CMinMachine::output(Node * curNode)
{
    m_best = curNode->total_weight;

    for (int i = m_n - 1; i != -1; i--)
    {
        m_select_best[i] = curNode->supplier_id;
        curNode = curNode->parent;
    }
}

bool CMinMachine::IsOK(int cur_price)
{
    return cur_price <= m_d;
}

3.3.Main.cpp

// -------------------------【chp 6       】----------------------
// @ author ： zhyh2010
// @ date ： 20150524
// @ version ： 1.0
// @ description ：          
// @ idea ：      
// -----------------------------------【end tip】-------------------------------

#include "MinMachine.h"
#include <iostream>

void main()
{
    CMinMachine instance;
    int res = instance.solve();
    std::cout << "res = " << res << std::endl;
}

4.参考内容最小重量機械設計問題5_1 6_4
STLの神器、優先行列