このサイトを使用するのは初めてなので、フォーマットが不適切であったり、変な表現があったりして申し訳ありません。このサイトのルールに準拠するように最善を尽くしますが、最初は間違いを犯す可能性があります。
私は現在、STL コンテナーを使用して C++ でいくつかの異なるビン パッキング アルゴリズムの実装に取り組んでいます。現在のコードには、修正が必要な論理的な障害がまだいくつかありますが、この質問はプログラムの構造に関するものです。論理的な障害の数を最小限に抑え、可能な限り読みやすくするためにプログラムをどのように構築する必要があるかについて、セカンドオピニオンを求めたくはありません。現在の状態では、これが最善の方法ではないと感じていますが、現在、コードを記述する他の方法は実際には見当たりません。
この問題は、動的なオンライン ビン パッキングの問題です。アイテムが割り当てられたビンを離れる前に、アイテムが任意の時間を持つという意味で動的です。
要するに、私の質問は次のとおり
です。ビン パッキング アルゴリズムの構造は C++ でどのように見えるでしょうか?
STL コンテナは、実装で任意の長さの入力を処理できるようにするための優れたツールですか?
コンテナーを読みやすく、実装しやすい方法で処理するにはどうすればよいですか?
私自身のコードについてのいくつかの考え:
クラスを使用して、さまざまなビンのリストとそれらのビン内のアイテムのリストの処理を適切に区別します。
実装を可能な限り効果的にする。
ベンチマーク用に、さまざまなデータ長とファイルで簡単に実行できます。
#include <iostream>
#include <fstream>
#include <list>
#include <queue>
#include <string>
#include <vector>
using namespace std;
struct type_item {
int size;
int life;
bool operator < (const type_item& input)
{
return size < input.size;
}
};
class Class_bin {
double load;
list<type_item> contents;
list<type_item>::iterator i;
public:
Class_bin ();
bool operator < (Class_bin);
bool full (type_item);
void push_bin (type_item);
double check_load ();
void check_dead ();
void print_bin ();
};
Class_bin::Class_bin () {
load=0.0;
}
bool Class_bin::operator < (Class_bin input){
return load < input.load;
}
bool Class_bin::full (type_item input) {
if (load+(1.0/(double) input.size)>1) {
return false;
}
else {
return true;
}
}
void Class_bin::push_bin (type_item input) {
int sum=0;
contents.push_back(input);
for (i=contents.begin(); i!=contents.end(); ++i) {
sum+=i->size;
}
load+=1.0/(double) sum;
}
double Class_bin::check_load () {
return load;
}
void Class_bin::check_dead () {
for (i=contents.begin(); i!=contents.end(); ++i) {
i->life--;
if (i->life==0) {
contents.erase(i);
}
}
}
void Class_bin::print_bin () {
for (i=contents.begin (); i!=contents.end (); ++i) {
cout << i->size << " ";
}
}
class Class_list_of_bins {
list<Class_bin> list_of_bins;
list<Class_bin>::iterator i;
public:
void push_list (type_item);
void sort_list ();
void check_dead ();
void print_list ();
private:
Class_bin new_bin (type_item);
bool comparator (type_item, type_item);
};
Class_bin Class_list_of_bins::new_bin (type_item input) {
Class_bin temp;
temp.push_bin (input);
return temp;
}
void Class_list_of_bins::push_list (type_item input) {
if (list_of_bins.empty ()) {
list_of_bins.push_front (new_bin(input));
return;
}
for (i=list_of_bins.begin (); i!=list_of_bins.end (); ++i) {
if (!i->full (input)) {
i->push_bin (input);
return;
}
}
list_of_bins.push_front (new_bin(input));
}
void Class_list_of_bins::sort_list () {
list_of_bins.sort();
}
void Class_list_of_bins::check_dead () {
for (i=list_of_bins.begin (); i !=list_of_bins.end (); ++i) {
i->check_dead ();
}
}
void Class_list_of_bins::print_list () {
for (i=list_of_bins.begin (); i!=list_of_bins.end (); ++i) {
i->print_bin ();
cout << "\n";
}
}
int main () {
int i, number_of_items;
type_item buffer;
Class_list_of_bins bins;
queue<type_item> input;
string filename;
fstream file;
cout << "Input file name: ";
cin >> filename;
cout << endl;
file.open (filename.c_str(), ios::in);
file >> number_of_items;
for (i=0; i<number_of_items; ++i) {
file >> buffer.size;
file >> buffer.life;
input.push (buffer);
}
file.close ();
while (!input.empty ()) {
buffer=input.front ();
input.pop ();
bins.push_list (buffer);
}
bins.print_list ();
return 0;
}
これは私のコードの単なるスナップショットであり、まだ正しく実行されていないことに注意してください
関係のないおしゃべりでこれを混乱させたくないだけです。貢献してくれた人々に感謝したいだけです。コードを見直して、プログラミングをもう少しうまく構築できるようになることを願っています。