Public feed
#604041
/***************************** * 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;}