Реализация упаковки бина в C ++ с использованием First Fit

Я делаю проект для университета, но я столкнулся с исключением, которое я не понимаю. Я использую алгоритмы S.Sahni, поэтому в основном я получил код из его книги. Я пытаюсь реализовать задачу Bin Packing с помощью First Fit, пока я использую деревья турниров (максимальный победитель).
Вот мой заголовок:

// file winner.h#ifndef WinnerTree_
#define WinnerTree_

#include <iostream>
#include <stdlib.h>
#include "xcept.h"
using namespace std;

template<class T>
class WinnerTree {
public:
WinnerTree(int TreeSize = 10);
~WinnerTree() {delete [] t;}
void Initialize(T a[], int size, int (&winner)(T a[], int player1, int player2));
int Winner()
{return (n) ? t[1] : 0;}
int Winner(int i)
{return (i < n) ? t[i] : 0;}
void RePlay(int i, int (&winner)(T a[], int player1, int player2));
void Output();
private:
int MaxSize;
int n;      // current size
int LowExt; // lowest-level external nodes
int offset; // 2^k - 1
int *t;     // array for winner tree
T *e;       // element array
void Play(int p, int lc, int rc, int (&winner)(T a[], int player1, int player2));
};

template<class T>
WinnerTree<T>::WinnerTree(int TreeSize)
{// Constructor for winner tree.
MaxSize = TreeSize;
t = new int[MaxSize];
n = 0;
}

template<class T>
void WinnerTree<T>::Initialize(T a[], int size, int (&winner)(T a[], int player1, int player2))
{// Initialize winner t for array a.
if (size > MaxSize || size < 2)
throw BadInput();
n = size;
e = a;

// compute  s = 2^log (n-1)
int i, s;
for (s = 1; 2*s <= n-1; s += s);

LowExt = 2*(n-s);
offset = 2*s-1;

// play matches for lowest-level external nodes
for (i = 2; i <= LowExt; i += 2)
Play((offset+i)/2, i-1, i, winner);

// handle remaining external nodes
if (n % 2) {// special case for odd n, play
// internal and external node
Play(n/2, t[n-1], LowExt+1, winner);
i = LowExt+3;}
else
i = LowExt+2;

// i is left-most remaining external node
for (; i <= n; i += 2)
Play((i-LowExt+n-1)/2, i-1, i, winner);
}

template<class T>
void WinnerTree<T>::Play(int p, int lc, int rc, int (&winner)(T a[], int player1, int player2))
{// Play matches beginning at t[p].
// lc and rc are the children of t[p].
t[p] = winner(e, lc, rc);

// more matches possible if at right child
while (p > 1 && p % 2) {// at a right child
t[p/2] = winner(e, t[p-1], t[p]);
p /= 2;  // go to parent
}
}

template<class T>
void WinnerTree<T>::RePlay(int i, int(&winner)(T a[], int player1, int player2))
{// Replay matches for element i.
if (i <= 0 || i > n)
throw OutOfBounds();

int p,   // match node
lc,  // left child of p
rc;  // right child of p

// find first match node and its children
if (i <= LowExt) {// begin at lowest level
p = (offset + i)/2;
lc = 2*p - offset; // left child of p
rc = lc+1;}
else {
p = (i-LowExt+n-1)/2;
if (2*p == n-1) {
lc = t[2*p];
rc = i;}
else {
lc = 2*p - n + 1 + LowExt;
rc = lc+1;}
}

t[p] = winner(e, lc, rc);

// play remaining matches
p /= 2;  // move to parent
for (; p >= 1; p /= 2)
t[p] = winner(e, t[2*p], t[2*p+1]);
}

template<class T>
void WinnerTree<T>::Output()
{
cout << "size = "<< n << " LowExt = " << LowExt
<< " Offset = " << offset << endl;
cout << "Winner tree pointers are" << endl;
for (int i = 1; i < n; i++)
cout << t[i] << ' ';
cout << endl;
}

#endif

Это мой файл исключений:

#ifndef Xcept_
#define Xcept_

#include <exception>
#include <new.h>

// bad initializers
class BadInitializers {
public:
BadInitializers() {}
};

// insufficient memory
class NoMem {
public:
NoMem() {}
};

// change new to throw NoMem instead of xalloc
void my_new_handler()
{
throw NoMem();
};

new_handler Old_Handler_ = set_new_handler(my_new_handler);

// improper array, find, insert, or delete index
// or deletion from empty structure
class OutOfBounds {
public:
OutOfBounds() {}
};

// use when operands should have matching size
class SizeMismatch {
public:
SizeMismatch() {}
};

// use when zero was expected
class MustBeZero {
public:
MustBeZero() {}
};

// use when zero was expected
class BadInput {
public:
BadInput() {}
};

#endif

И это моя основная функция:

// First fit bin packing

#include "stdafx.h"

using namespace std;

#include <iostream>
#include "winner.h"
int winner(int a[], int player1, int player2)
{// For a max winner tree.
if (a[player1] >= a[player2])
return player1;
return player2;
}

void FirstFitPack(int s[], int n, int c)
{// Output first fit packing into bins of size c.
// n is the number of objects and s[] their size.

WinnerTree<int> *W = new WinnerTree<int>(n);
int *avail = new int[n + 1]; // bins

// initialize n bins and winner tree
for (int i = 1; i <= n; i++)
avail[i] = c;  // initial available capacity
W->Initialize(avail, n, winner);

// put objects in bins
for (int i = 1; i <= n; i++) {// put s[i] in a bin
// find first bin with enough capacity
int p = 2;  // start search at left child of root
while (p < n) {
int winp = W->Winner(p);
if (avail[winp] < s[i])  // first bin is in
p++;                 // right subtree
p *= 2;   // move to left child
}

int b;   // will be set to bin to use
p /= 2;  // undo last left child move
if (p < n) {// at a tree node
b = W->Winner(p);
// if b is right child, need to check
// bin b-1.  No harm done by checking
// bin b-1 even if b is left child.
if (b > 1 && avail[b - 1] >= s[i])
b--;
}
else  // arises when n is odd
b = W->Winner(p / 2);

cout << "Pack object " << i << " in bin "<< b << endl;
avail[b] -= s[i];  // update avail. capacity
W->RePlay(b, winner);
getchar();
}
}

int main(void)
{
int n, c; // number of objects and bin capacity
cout << "Enter number of objects" << endl;
cin >> n;
if (n < 2) {
cout << "Too few objects" << endl;
exit(1);
}
cout << "Enter bin capacity" << endl;
cin >> c;

int *s = new int[n + 1];

for (int i = 1; i <= n; i++) {
cout << "Enter space requirement of object " << i << endl;
cin >> s[i];
if (s[i] > c) {
cout << "Object too large to fit in a bin" << endl;
exit(1);
}
}
FirstFitPack(s, n, c);
return 0;
}

Исключение, которое я получаю:
Исключение первого шанса в 0x0012668D в Bin Packing-FF.exe: 0xC0000005: расположение чтения нарушения доступа 0xF9039464.

Я знаю, что получаю это исключение из-за победителя. Но я не могу понять, что я должен изменить здесь.

int winner(int a[], int player1, int player2)
{// For a max winner tree.
if (a[player1] >= a[player2])
return player1;
return player2;
}

Кроме того, если я нажимаю пробел или ввод после последнего ввода (объекта), то я не получаю исключения, и все идет гладко. Но все же я хочу знать, почему я получаю это исключение.

Заранее спасибо.

0

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …