箱最適化マッチング、データ構造(c++)

ある運送会社はn個の物品をm個の箱に入れなければならない.各物品には一定の重量があり、各箱には容量制限があり、どのようにして最小の箱で物品を積むのか.説明:各箱の容量はMであり、物品iが占有する箱の容量はW[i]、0<=W[i]<=Mである.最適マッチング法:箱jの使用可能量をb[j]とし、物品iは使用可能容量が最小であるがw[i]未満ではない箱に入れるべきである.最適マッチング法は,二叉ルックアップツリーを用いて実現した.機能要求及び説明:(1)各箱に与えられた残容量は、残容量の大きさに応じて二叉ルックアップツリーを構築する.(2)所与の各物品の重量wiは、入れるべき物品が占有する箱容量w[i]に応じて、二叉ルックアップツリーで最適な箱を検索し、その箱の残容量を修正する.(3)選択した箱を二叉検索木から削除する.(4)容量を減らした箱を二叉ルックアップツリーに挿入する.(5)最終的な梱包結果を印刷する;(6)モジュール化設計を採用し,上記各機能をそれぞれ関数形式で記述する.

class BSTNode {
     
private:
   	int key; //    
	int value;//    
	BSTNode* ln;//    
	BSTNode* rn;
public:
    //      
	BSTNode() {
     
		ln = rn = NULL;
	}
	//      
	BSTNode(int key, int a, BSTNode* ln = NULL, BSTNode* rn = NULL) :key(key), value(a), ln(ln), rn(rn) {
     }
	inline int getValue();//      
	inline void setValue(int value) ;//      
	inline int getKey();//      
	inline void setKey(int key);//      
inline BSTNode* left();//       
	inline void setLeft(BSTNode* ln) ;//       
	inline BSTNode* right() ;//       
	inline void setRight(BSTNode* rn) ;//       
};
class BST {
     
private:
	BSTNode* inserthelp(BSTNode*, int&, int&);//        
	BSTNode* removehelp(BSTNode*, int&);//        
	void printhelp(BSTNode* root);//         
	BSTNode* getmin(BSTNode*);//      
	BSTNode* deletemin(BSTNode*);//      
	BSTNode* findhelp(BSTNode*, int&);//    
	void clearhelp(BSTNode*);//     
public:
    BSTNode* root;//      
	int m;//    
	int *a = new int[MAX];//            
	BST() {
     root = NULL;}//    
	BST(int m){
     //    
	    root = NULL;
	    this->m = m;
	}
	~BST() {
     clearhelp(root);}	//    
	void insert(int key, int value);//      
	void remove(int key) ;//      
	BSTNode findGE(int key) ;//        
	void findMin(int* a, int n) ;//     
	void print()//     
	int numUserB(int A[]);//                
};
2、      
        ：        ，        ，                。
       ：                             。
             ，                          。
              ，               n，       n        ，  n         n      ，                  ，  n          ，                   ，           ，                      ，             ，      ，                     。
       
#include 
#include 
using namespace std;
#define MAX  999
//     
class BSTNode {
     
private:
    //    
	int key;
	//    
	int value;
	//    
	BSTNode* ln;
	BSTNode* rn;
public:
    //      
	BSTNode() {
     
		ln = rn = NULL;
	}
	//      
	BSTNode(int key, int a, BSTNode* ln = NULL, BSTNode* rn = NULL) :key(key), value(a), ln(ln), rn(rn) {
     
	}
	~BSTNode() {
     
	}
	//      
	inline int getValue() {
     
		return this->value;
	}
	//      
	inline void setValue(int value) {
     
		this->value = value;
	}
	//      
	inline int getKey() {
     
		return key;
	}
	//      
	inline void setKey(int key) {
     
		this->key = key;
	}
	//       
	inline BSTNode* left() {
     
		return ln;
	}
	//       
	inline void setLeft(BSTNode* ln) {
     
		this->ln = ln;
	}
	//       
	inline BSTNode* right() {
     
		return rn;
	}
	//       
	inline void setRight(BSTNode* rn) {
     
		this->rn = rn;
	}
};
 
//     
class BST {
     
private:
    //        
	BSTNode* inserthelp(BSTNode*, int&, int&);
	//        
	BSTNode* removehelp(BSTNode*, int&);
	//         
	void printhelp(BSTNode* root);
	//      
	BSTNode* getmin(BSTNode*);
	//      
	BSTNode* deletemin(BSTNode*);
	//    
	BSTNode* findhelp(BSTNode*, int&);
	//     
	void clearhelp(BSTNode*);
public:
    //      
	BSTNode* root;
	//    
	int m;
	//            
	int *a = new int[MAX];
	//    
	BST() {
     
		root = NULL;
	}
	//    
	BST(int m){
     
	    root = NULL;
	    this->m = m;
	}
	//    
	~BST() {
     
		clearhelp(root);
	}
	//      
	void insert(int key, int value) {
     
		root = inserthelp(root, key, value);
	}
	//      
	void remove(int key) {
     
			removehelp(root, key);
	}
	//        
	BSTNode findGE(int key) {
     
		BSTNode* node = root;
		BSTNode a;
		while (node != NULL) {
     
			if (node->getKey() >= key) {
     
				a = *node;
				node = node->left();
			}
			else
				node = node->right();
		}
		return a;
	}
	//     
	void findMin(int* a, int n) {
     
		BSTNode B;
		for (int i = 0; i < n; i++) {
     
			B = findGE(a[i]);
			//          
			remove(B.getKey());
			//        
			insert(B.getKey()-a[i], B.getValue());
		}
	}
	//     
	void print() {
     
        cout<<"   "<<"   "<<endl;
		if (root != NULL)
			printhelp(root);
	}
	//                
    int numUserB(int A[]){
     
        cout<<"             "<<endl;
        int number = 0;
        for(int i = 0;i<m;i++){
     
            if(A[i] != a[i]){
     
                cout<<i<<" ";
                number++;
            }
        }
        cout<<endl;
        return number;
    }
};
//         
void BST::printhelp(BSTNode* root) {
     
	if (root == NULL) return;
	printhelp(root->left());
	a[root->getValue()] = root->getKey();
	cout << root->getValue()<<"   "<<root->getKey() << endl;
	printhelp(root->right());
}
//      
BSTNode* BST::getmin(BSTNode* root) {
     
	if (root->left() == NULL) return root; else return getmin(root->left());
}
//      
BSTNode* BST::deletemin(BSTNode* root) {
     
	if (root->left() == NULL) return root->right(); else root->setLeft(deletemin(root->left()));
	return root;
}
//      
BSTNode* BST::removehelp(BSTNode* root, int& key) {
     
	if (root == NULL) return NULL;
	else if (key < root->getKey())
		root->setLeft(removehelp(root->left(), key));
    else if (key > root->getKey())
		root->setRight(removehelp(root->right(), key));
    else {
     
		BSTNode* temp = root;
		if (root->left() == NULL) {
     
			root = root->right();
			delete temp;
		}
		else if (root->right() == NULL) {
     
			root = root->left();
			delete temp;
		}
		else {
     
			BSTNode* t = getmin(root->right());
			root->setValue(t->getValue());
			root->setKey(t->getKey());
			root->setRight(deletemin(root->right()));
			delete t;
		}
	}
	return root;
}
//      
BSTNode* BST::inserthelp(BSTNode* root, int& key, int &value) {
     
	if (root == NULL) return new BSTNode(key, value);
	if (key < root->getKey()) root->setLeft(inserthelp(root->left(), key, value));
	else root->setRight(inserthelp(root->right(), key, value));
	return root;
}
//     
void BST::clearhelp(BSTNode* root) {
     
	if (root == NULL) return;
	clearhelp(root->left());
	clearhelp(root->right());
	delete root;
}
//   
int main() {
     
    //   
	int m;
	cout << "      m=";
	cin >> m;
	//    
	int b[MAX];
	BST r(m);
	cout << "         " << endl;
	for (int i = 0; i < m; i++) {
     
		cin >> b[i];
		r.insert(b[i], i);
	}
	//   
	int n;
	cout << "       n=";
	cin >> n;
	//    
	int w[MAX];
	cout << "           " << endl;
	for (int i = 0; i < n; i++)
		cin >> w[i];
    cout<<"         "<<endl;
	r.print();
	r.findMin(w, n);
	cout<<"               "<<endl;
	r.print();
	int number = r.numUserB(b);
	cout<<"         "<<number<<endl;
}

レポートリンク