Advertisement
ismaeil

questions

Jan 17th, 2020
164
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.80 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <windows.h>
  3.  
  4. using namespace std;
  5.  
  6. int optMark ;
  7. bool cur[5] ,optimal[5];
  8.  
  9. bool checkOptimal( int curMark ){
  10.     return ( curMark > optMark );
  11. }
  12.  
  13. void BT(int curV , int curTime , int curMark , int fullTime , int time[] , int mark[] ){
  14.  
  15.     if( curTime + time[ curV ] <= fullTime ){
  16.  
  17. /// --- ADD THIS VALUE TO ANSWER --- ///
  18.         cur[ curV ] = true;
  19.         if( curV < 4 ){
  20.             BT( curV+1 , curTime+time[curV] , curMark+mark[curV] , fullTime , time , mark );
  21.         }else if (curV == 4){
  22.             if( checkOptimal( curMark ) ){
  23.                 optMark = curMark;
  24.                 for( int i=0 ; i<5 ; i++)
  25.                     optimal[i] = cur[i];
  26.             }
  27.         }
  28.         cur[ curV ] = false;
  29.  
  30. /// --- TRY WITHOUT ADD THIS VALUE TO ANSWER --- ///
  31.         if( curV < 4 ){
  32.             BT( curV+1 , curTime , curMark , fullTime , time , mark );
  33.         }else if (curV == 4){
  34.             if( checkOptimal( curMark ) ){
  35.                 optMark = curMark;
  36.                 for( int i=0 ; i<5 ; i++)
  37.                     optimal[i] = cur[i];
  38.             }
  39.         }
  40.     }
  41.  
  42.     else if( curTime + time[ curV ] > fullTime ){
  43.         if( curV < 4 ){
  44.             BT( curV+1 , curTime , curMark , fullTime , time , mark );
  45.         }else if (curV == 4){
  46.             if( checkOptimal( curMark ) ){
  47.                 optMark = curMark;
  48.                 for( int i=0 ; i<5 ; i++)
  49.                     optimal[i] = cur[i];
  50.             }
  51.         }
  52.     }
  53. }
  54.  
  55. int main(){
  56.     int time[5] = { 15 ,10 , 5, 20 , 5 };
  57.     int mark[5] = { 10 ,10 ,10, 30  ,15};
  58.  
  59.     BT( 0 , 0 , 0 , 30 , time , mark );
  60.  
  61.     cout << "Optimal Mark Solution = " << optMark << endl;
  62.     for(int i=0 ; i<5 ; i++){
  63.         cout << " " << optimal[i];
  64.     }
  65.  
  66.     return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement