Từ 1 tới 7 trên tổng số 7 kết quả

Đề tài: Làm bài toán cái ba lô bằng hướng đối tượng C++ như thế nào?

  1. #1
    Ngày gia nhập
    10 2008
    Bài viết
    2

    Unhappy Làm bài toán cái ba lô bằng hướng đối tượng C++ như thế nào?

    em có bài toán cái ba lô sau:cho một cái ba lo có thể đựng trọng lượng W và n loại đồ vật ,mỗi đồ vật i có một trọng lượng gi và một giá trị vi.tất cả đồ vật có số lượng ko hạn chế.tìm cách lựa chọn các đồ vật đựung vào ba lô,chọn các loại đồ vật nào,mỗi loại lấy bao nhiu sao cho tổng tong lượng ba lô ko vượt quá W và tổng giá trị lớn nhất (dùng kĩ thuật nhánh cận và số liệu ko nhập từ bàn phím mà dùng truy xuất vào file text riêng). Mấy anh pro nào làm giúp em bằng hướng đối tượng nha hix em gần thi rồi mà cái này hok bít.
    em ví dụ 1 file text để truy xuất vào chương trình chạy:
    37 //tổng trọng lượng ba lô
    3 40 A //trọng lượng giá trị tên đồ vật là A
    2 23 B
    4 4 C
    4 63 D
    cái này em làm niên luận ai ANH Chị nào pro hiểu bít nh` thì giúp em với nha cám ơn nh nh nh nh lắm (em là thành viên mới chưa bít nh mong giúp đỡ)

  2. #2
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    - Kĩ thuật nhánh cận là dùng backtracking + điều kiện để cắt nhánh thế thôi, cậu google với từ khóa : branch_bound algorithm để đọc và tìm hiểu, vì nó cũng dài và có rất nhiều rồi nên tui sẽ không thể giải thích từ A-Z cho cậu được. Về làm hướng đối tượng thì nó cũng không quá phức tạp, cậu chịu khó vẽ nó ra giấy theo mô hình thiết kế UML thì sẽ dễ dàng hơn.
    - Tui cho cậu 1 project của tui làm khoá trước, nhưng bài của tui không dùng kĩ thuật nhánh cận và cũng không giống yêu cầu đề bài của cậu. Bài của tui là 1 biến thế của bài toán cái túi. Tui dùng giải thuật tham lam kết hợp với hàng đợi ưu tiên ở đây, tui sẽ cho cậu code hết để cậu hình dung thiết kế OOP như thế nào.
    - Cậu muốn biến bài tui thành bài của cậu thì cũng phải suy nghĩ và edit lại rất nhiều, nếu cậu chịu khó viết, tui sẽ coi và góp ý cho cậu, nếu không thì tùy cậu vậy
    BinaryHeap.h

    C++ Code:
    1. #include <stdexcept>
    2. #include <string>
    3. #include <vector>
    4. #include <algorithm>
    5. #include <iostream>
    6. #include <iterator>
    7.  
    8. using namespace std;
    9.  
    10. /*
    11.     Class Heap Exception
    12. */
    13. class HeapException : public logic_error
    14. {
    15. public :
    16.     HeapException( const string& mes = "" )
    17.         :logic_error( mes.c_str() )
    18.     {   }
    19. };
    20.  
    21. /*
    22.     Class Binary Heap
    23. */
    24. template< class T >
    25. class BinaryHeap
    26. {
    27. public :
    28.     BinaryHeap();
    29.     virtual ~BinaryHeap();
    30. public :
    31.     virtual bool hIsEmpty() const;
    32.     virtual void hInsert( const T& new_item );
    33.     virtual void hDelete( T& root_item )
    34.         throw( HeapException );
    35.     virtual void hPrint( ostream& o ) const;
    36. protected :
    37.     void         hRebuild( int root );
    38. private :
    39.     vector< T > m_items;
    40.     int         m_size;
    41. };
    42.  
    43. template< class T >
    44. BinaryHeap< T >::BinaryHeap()
    45.     :m_size( 0 )
    46. {   }
    47.  
    48. template< class T >
    49. BinaryHeap< T >::~BinaryHeap()
    50. {   }
    51.  
    52. template< class T >
    53. bool BinaryHeap< T >::hIsEmpty() const
    54. {
    55.     return m_size == 0;
    56. }
    57.  
    58. template< class T >
    59. void BinaryHeap< T >::hInsert( const T& new_item )
    60. {
    61.     m_items.push_back( new_item );
    62.  
    63.     int place  = m_size;
    64.     int parent = ( place - 1 ) / 2;
    65.  
    66.     while( parent >= 0 && m_items[ place ] > m_items[ parent ] )
    67.     {
    68.         swap( m_items[ place ], m_items[ parent ] );
    69.  
    70.         place  = parent;
    71.         parent = ( place - 1 ) / 2;
    72.     }
    73.  
    74.     ++m_size;
    75.     m_items.resize( m_size );
    76. }
    77.  
    78. template< class T >
    79. void BinaryHeap< T >::hDelete( T& root_item )
    80.     throw( HeapException )
    81. {
    82.     if( hIsEmpty() )
    83.     {
    84.         throw HeapException( "[ hDelete ] : exception heap empty" );
    85.     }
    86.     else
    87.     {
    88.         root_item    = m_items[ 0 ];
    89.         m_items[ 0 ] = m_items[ --m_size ];
    90.         hRebuild( 0 );
    91.     }
    92. }
    93.  
    94. template< class T >
    95. void BinaryHeap< T >::hRebuild( int root )
    96. {
    97.     int child = ( root * 2 ) + 1;
    98.  
    99.     if( child < m_size )
    100.     {
    101.         int right_child = child + 1;
    102.  
    103.         if( ( right_child < m_size )  && m_items[ right_child ] > m_items[ child ] )
    104.         {
    105.             child = right_child;
    106.         }
    107.         if( m_items[ root ] < m_items[ child ] )
    108.         {
    109.             swap( m_items[ root ], m_items[ child ] );
    110.  
    111.             // recursive called
    112.             hRebuild( child );
    113.         }
    114.     }
    115. }
    116.  
    117. template< class T >
    118. void BinaryHeap< T >::hPrint( ostream& o ) const
    119. {
    120.     copy( m_items.begin(), m_items.end(), ostream_iterator< T >( o, " " ) );
    121.     o << endl;
    122. }
    PriorityQueue.h
    C++ Code:
    1. #include "BinaryHeap.h"
    2.  
    3. /*
    4.     Class Priority Queue Exception
    5. */
    6. class PQueueException : public logic_error
    7. {
    8. public :
    9.     PQueueException( const string& mes = "" )
    10.         :logic_error( mes.c_str() )
    11.     {   }
    12. };
    13.  
    14. /*
    15.     Class Priority Queue
    16. */
    17. template< class T >
    18. class PriorityQueue
    19. {
    20. public :
    21.     PriorityQueue();
    22.     virtual ~PriorityQueue();
    23. public :
    24.     virtual bool pqIsEmpty() const;
    25.     virtual void pqInsert( const T& new_item );
    26.     virtual void pqDelete( T& it )
    27.         throw( PQueueException );
    28. private :
    29.     BinaryHeap< T > m_heap;
    30.  
    31. template< class Tr >
    32. friend
    33.     ostream& operator <<( ostream& o, const PriorityQueue< Tr >& pq );
    34. };
    35.  
    36. template< class T >
    37. PriorityQueue< T >::PriorityQueue()
    38. {  }
    39.  
    40. template< class T >
    41. PriorityQueue< T >::~PriorityQueue()
    42. {  }
    43.  
    44. template< class T >
    45. bool PriorityQueue< T >::pqIsEmpty() const
    46. {
    47.     return m_heap.hIsEmpty();
    48. }
    49.  
    50. template< class T >
    51. void PriorityQueue< T >::pqInsert( const T& nit )
    52. {
    53.     m_heap.hInsert( nit );
    54. }
    55.  
    56. template< class T >
    57. void PriorityQueue< T >::pqDelete( T& it )
    58.     throw( PQueueException )
    59. {
    60.     try
    61.     {
    62.         m_heap.hDelete( it );
    63.     }
    64.     catch( HeapException ex )
    65.     {
    66.         throw PQueueException( "[ pqDelete ] exception queue empty" );
    67.     }
    68. }
    69.  
    70. template< class T >
    71. ostream& operator <<( ostream& o, const PriorityQueue< T >& pq )
    72. {
    73.     if( pq.pqIsEmpty() )
    74.         o << " --- " << endl;
    75.     else
    76.         ( pq.m_heap ).hPrint( o );
    77.  
    78.     return o;
    79. }

  3. #3
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Box.h
    C++ Code:
    1. #ifndef BOX_H
    2. #define BOX_H
    3.  
    4. #include <string>
    5. #include <stdexcept>
    6. #include <vector>
    7. #include <algorithm>
    8. #include <functional>
    9. #include <iterator>
    10.  
    11. using namespace std;
    12.  
    13. const double MAX_WEIGHT = 1.0;
    14.  
    15. class WeightException : public logic_error
    16. {
    17. public :
    18.     WeightException( const string& mes )
    19.         :logic_error( mes.c_str() )
    20.     {   }
    21. };
    22.  
    23. class Box
    24. {
    25. private :
    26.     double           m_max_weight;
    27.     int              m_seqnum;
    28.     double           m_totload;
    29.     vector< double > m_loads;
    30. public :
    31.     Box()
    32.         :m_max_weight( 0.0 ), m_seqnum( 0 ), m_totload( 0.0 )
    33.     {   }
    34.     Box( double max_weight, int seqnum )
    35.         :m_max_weight( max_weight ), m_seqnum( seqnum ), m_totload( 0.0 )
    36.     {   }
    37. public :
    38.     int    getSeqnum() const;
    39.     double getTotLoad() const;
    40.     double getMaxWeight() const;
    41.     bool   addItem( double it )
    42.         throw( WeightException );
    43.     bool   isBoxEmpty() const;
    44. public :
    45.     bool operator !=( const Box& rhs ) const;
    46.     bool operator ==( const Box& rhs ) const;
    47.     bool operator  <( const Box& rhs ) const;
    48.     bool operator  >( const Box& rhs ) const;
    49. friend
    50.     ostream& operator <<( ostream& o, const Box& box );
    51. };
    52.  
    53. #endif

    Box.cpp
    C++ Code:
    1. #include "Box.h"
    2.  
    3. int Box::getSeqnum() const
    4. {
    5.     return m_seqnum;
    6. }
    7.  
    8. double Box::getTotLoad() const
    9. {
    10.     return m_totload;
    11. }
    12.  
    13. double Box::getMaxWeight() const
    14. {
    15.     return m_max_weight;
    16. }
    17.  
    18. bool Box::addItem( double it )
    19.     throw( WeightException )
    20. {
    21.     if( ( m_totload + it ) > m_max_weight )
    22.     {
    23.         return false;
    24.     }
    25.     else if( it < 0.0 )
    26.     {
    27.         throw WeightException( "[ addItem ] exception negative weight" );
    28.         return false;
    29.     }
    30.     else
    31.     {
    32.         int curr_items = m_loads.size();
    33.         m_totload      = m_totload + it;
    34.         m_loads.push_back( it );
    35.         m_loads.resize( curr_items + 1 );
    36.         return true;
    37.     }
    38. }
    39.  
    40. bool Box::isBoxEmpty() const
    41. {
    42.     return m_totload == 0.0;
    43. }
    44.  
    45. bool Box::operator !=( const Box& rhs ) const
    46. {
    47.     return m_totload != rhs.m_totload;
    48. }
    49.  
    50. bool Box::operator ==( const Box& rhs ) const
    51. {
    52.     return m_totload == rhs.m_totload;
    53. }
    54.  
    55. bool Box::operator <( const Box& rhs ) const
    56. {
    57.     return m_totload < rhs.m_totload;
    58. }
    59.  
    60. bool Box::operator >( const Box& rhs ) const
    61. {
    62.     return m_totload > rhs.m_totload;
    63. }
    64.  
    65. ostream& operator <<( ostream& o, const Box& box )
    66. {
    67.     o << " -- The " << box.m_seqnum << endl;
    68.     copy( ( box.m_loads ).begin(), ( box.m_loads ).end(), ostream_iterator< double >( o, " - " ) );
    69.     o << "\n --> and total loaded : " << box.m_totload;
    70.     return o << endl;
    71. }
    Đã được chỉnh sửa lần cuối bởi rox_rook : 13-10-2008 lúc 07:12 AM.

  4. #4
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    KnapStack.h
    C++ Code:
    1. #ifndef KNAPSTACK_H
    2. #define KNAPSTACK_H
    3.  
    4. #include "PriorityQueue.h"
    5. #include "TopicEData.h"
    6.  
    7. #include <fstream>
    8.  
    9. using namespace std;
    10.  
    11. class FileException : public logic_error
    12. {
    13. public :
    14.     FileException( const string& mes )
    15.         :logic_error( mes.c_str() )
    16.     {   }
    17. };
    18.  
    19. class KnapStack
    20. {
    21. private :
    22.     vector< double >     m_items;
    23.     int                  m_num_items;
    24.     PriorityQueue< Box > m_con;
    25.     ifstream             m_inf;
    26. public :
    27.     KnapStack();
    28. public :
    29.     string getInputFileName() const;
    30.     void   openInputFile( const string& fin )
    31.         throw( FileException );
    32.     void   readDataFromFile( const string& fin );
    33.     void   solveForLeastBoxes();
    34.     void   showResult();
    35. static
    36.     bool isNegative( double x )
    37.     {
    38.         return ( x < 0 );
    39.     }
    40. };
    41.  
    42. #endif

    KnapStack.cpp
    C++ Code:
    1. #include "KnapStack.h"
    2.  
    3. KnapStack::KnapStack()
    4. {   }
    5.  
    6. string KnapStack::getInputFileName() const
    7. {
    8.     string fin;
    9.     std::cout << "Enter an input file name( no space ) : ";
    10.     cin >> fin;
    11.     return fin;
    12. }
    13.  
    14. void KnapStack::openInputFile( const string& fin )
    15.     throw( FileException )
    16. {
    17.     m_inf.open( fin.c_str() );
    18.     if( m_inf.fail() )
    19.         throw FileException( "...File could not found \n\n" );
    20.     else
    21.         cout << "\n..Open file for reading sucessfully \n\n";
    22. }
    23.  
    24. void KnapStack::readDataFromFile( const string& fin )
    25. {
    26.     double an_item;
    27.     while( m_inf >> an_item )
    28.     {
    29.         m_items.push_back( an_item );
    30.     }
    31.     vector< double >( m_items ).swap( m_items );
    32. }
    33.  
    34. void KnapStack::solveForLeastBoxes()
    35. {
    36.     sort( m_items.begin(), m_items.end(), greater< double >() );
    37.     vector< double > left_item_box( m_items );
    38.     cout << "\n\n THE TOTAL ITEMS = " << m_items.size();
    39.  
    40.     int index = 0;
    41.     int seq   = 1;
    42.     while( index < left_item_box.size() )
    43.     {
    44.         // create an empty box with maximum weight can load
    45.         // and its sequence number.
    46.         Box abox( MAX_WEIGHT, seq );
    47.         ++seq;
    48.         /*
    49.             For each box inser heaviest items
    50.             until it get overflowing
    51.         */
    52.         int TIMES = 0;
    53.         for( int i = 0; i < left_item_box.size(); ++i )
    54.         {
    55.             if( abox.addItem( left_item_box[ i ] ) == true )
    56.             {
    57.                 // make it bad value i.e negative
    58.                 // -1.0 is just an abitary number here
    59.                 left_item_box[ i ] = -1.0;
    60.             }
    61.  
    62.             // if can no longer added
    63.             if( i == ( left_item_box.size() - 1 ) )
    64.             {
    65.                 left_item_box.erase( remove_if( left_item_box.begin(), left_item_box.end(), KnapStack::isNegative ), left_item_box.end() );
    66.             }
    67.         }
    68.  
    69.         /*
    70.             Insert a box into priority queue "m_con"
    71.             if that box is not empty
    72.         */
    73.         if( abox.isBoxEmpty() == false )
    74.         {
    75.             m_con.pqInsert( abox );
    76.         }
    77.  
    78.         /*
    79.                 Sort all items again
    80.         */
    81.         sort( left_item_box.begin(), left_item_box.end(), greater< double >() );
    82.  
    83.         //reset index so that it check for the entire rest items.
    84.         index = 0;
    85.  
    86.     }
    87. }
    88.  
    89. void KnapStack::showResult()
    90. {
    91.     int i = 0;
    92.     while( !m_con.pqIsEmpty() )
    93.     {
    94.         i++;
    95.         Box inside_box;
    96.         m_con.pqDelete( inside_box );
    97.         cout << inside_box << "\n";
    98.     }
    99.  
    100.     cout << "\n The total boxes used = " << i;
    101. }


    Main.cpp

    C++ Code:
    1. #include <iostream>
    2. #include "KnapStack.h"
    3.  
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8.  
    9.     KnapStack k_prob;           // a Knapstack problem
    10.     string    input_file_name;  // an input file name
    11.  
    12.     // get input file name from user
    13.     input_file_name = k_prob.getInputFileName();
    14.  
    15.     // try to open file
    16.     try
    17.     {
    18.         k_prob.openInputFile( input_file_name );
    19.     }
    20.     catch( FileException fex )
    21.     {
    22.         cerr << fex.what() << " at line 158." << endl;
    23.         return EXIT_FAILURE;
    24.     }
    25.  
    26.     // if sucessfully open file, then read file data
    27.     k_prob.readDataFromFile( input_file_name );
    28.  
    29.     // solve knapstack problem for the least boxes
    30.     k_prob.solveForLeastBoxes();
    31.  
    32.     // show result
    33.     k_prob.showResult();
    34.  
    35.     return 0;
    36. }

    Search dưới nick của tui, hồi đó tui cũng có làm 1 bài hướng đối tượng dùng cả 2 kĩ thuật nhánh cận và quy hoạch động cho bài toán cái túi( dạng của cậu ). Kết hợp bài đó với bài này thì cậu có thể hoàn thành project của cậu dễ dàng ! Good luck !

  5. #5
    Ngày gia nhập
    10 2008
    Bài viết
    2

    uh mình cảm ơn bạn thật sự mình lập trình dỡ lắm hok bít dc hok nữa

  6. #6
    Ngày gia nhập
    05 2008
    Nơi ở
    tx tra vinh
    Bài viết
    9

    Mặc định Làm bài toán cái ba lô bằng hướng đối tượng C++ như thế nào?

    mình thông cảm với với bạn, mình cũng có thằng bạn ròm ko biết lập trình giống bạn vậy đó.

    Đề nghị bạn Cường xem lại cho kỹ trước khi copy, bài này ko phải là NHÁNH CẬN đâu đóa
    Mọi lý thuyết đều màu xám, chỉ có cây đời mãi xanh tươi !!!

  7. #7
    Ngày gia nhập
    09 2010
    Bài viết
    6

    Mặc định Sử dụng giải thuật tham lam cho bài toán cái túi.

    Anh ơi. code bài toán cái túi bằng giải thuật tham lam thế nào ạ?
    Em đọc và viết k được ạ?

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn