/*****************************
 * program Bài Toán Cái Ba Lô *
 ******************************/


#include <iostream>
#include <string>
//#include <conio.h>
#include <cstdio>
#include <iomanip>

using namespace std;

const int maxx = 100;

int Items[maxx];
int ItemsValue[maxx];
int ItemsWeight[maxx];

int X[maxx]; /*The optimized solution*/
int Try[maxx];

bool CHECK[maxx];


int ITEMS, WEIGHT;
int MaxVal;
int W, V;
 


void Ini()
{
        W = 0, V = 0;
        MaxVal = 0;
        /*Tat ca dò vat dèu có the chon*/
        for ( int i = 1; i < ITEMS; i++ )
        {
                CHECK[i] = true;
        }
}
void Branch_Bound ( int i ) 
{
        int T;
        int Temporary_Value;
        T = (int)((WEIGHT-W)/ItemsWeight[i]);
        
        for ( int j = T; j >= 0; j--)
        {
                //if ( CHECK[j] == true ) /*Néu chua chon dò vat dó*/
                //{
                        Try[i] = j; /*Thu chon các loai dò vât*/
                        
                        W = W + ItemsWeight[i]*Try[i]; /*Tang khoi luong trong túi*/
                        V = V + ItemsValue[i]*Try[i];  /*Giá tri cua túi*/
                         
                    
                        
                        if ( i == ITEMS ) /*Néu dã dat trong luong tói da
                                            Ghi nhan ket qua càn tìm*/
                        {
                                if ( V > MaxVal )
                                
                                for ( int a = 1; a <= ITEMS; a++ )
                                {
                                        X[a] = Try[a];
                                }
                                
                                MaxVal = V; /*Giá tri cuoi cùng cua túi*/
                                
                        }
                        else
                        { 
                                Temporary_Value = V + ItemsValue[i+1]*(WEIGHT - W)/ItemsWeight[i+1];
                                if (  Temporary_Value > MaxVal )
                                {
                                        Branch_Bound ( i + 1 );
                                }
                                       
                        }
                        W = W - ItemsWeight[i]*Try[i];
                        V = V - ItemsValue[i]*Try[i];
                //}
               
        }
}


void PrintResult()
{
        for ( int i = 1; i <= ITEMS; i++ )
        {
                cout << X[i] << setw(3);
        }
        cout << endl;
        cout << "Maximum Value is : "  << MaxVal << endl;
}

void main()
{
        cout << "How many Items:  "; cin >> ITEMS;
        cout << "Weight Maximum of your bags: "; cin >> WEIGHT;
      
        for ( int i = 1; i <= ITEMS; i++ )
        {
                cout << " The  [" << i << "] item weigh : ";
                cin  >> ItemsWeight[i];
                cout << " Its value is  :  ";
                cin  >> ItemsValue[i];
                cout << endl;
        }
      
     
      
        Ini();
      
        Branch_Bound(1);
        
        PrintResult();
      
          
        
        int r;
        cin >> r;
}