BT1.cpp

// BT1.cpp
#include <bits/stdc++.h>

using namespace std;

struct DienThoai {
	string nhanHieu;
	int kichThuoc;
	int giaBan;
};

int n = 5;
int s = 17;
int F[6][18];
DienThoai d[] = {
	{"Samsung", 5, 1000},
	{"Oppo", 6, 2000},
	{"iPhone", 4, 4000},
	{"Huawei", 7, 3000},
	{"Vertu", 8, 5000}
};

void LayDienThoai() {
	for (int j = 0; j <= s; j++) F[0][j] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= s; j++) {
			F[i][j] = F[i - 1][j];
			int temp = F[i - 1][j - d[i].kichThuoc] + d[i].giaBan;
			if (d[i].kichThuoc <= j && F[i][j] < temp) F[i][j] = temp;
		}
	}
}

void TruyVet() {
	int i = n; int j = s;
	cout << "Nhan hieu\tKich thuoc\tGia ban" << endl;
	while (i != 0) {
		if (F[i][j] != F[i - 1][j]) {
			cout << d[i].nhanHieu << "\t\t" << d[i].kichThuoc << "\t\t" << d[i].giaBan << endl;;
			j = j - d[i].kichThuoc;
		}
		i--;
	}
}

int TimKiem(DienThoai a[], int l, int r) {
	if (r == l) {
		//if (a[l].giaBan >= 3000 && a[l].giaBan <= 6000)	return 1;
		//return 0;
		return (a[l].giaBan >= 3000 && a[l].giaBan <= 6000);
	} else {
		int m = (l + r) / 2;
		return TimKiem(a, l, m) + TimKiem(a, m + 1, r);
	}
}

int main() {
	LayDienThoai();
	cout << "Gia ban lon nhat la: " << F[n][s] << endl;
	TruyVet();
	cout << "So luong dien thoai co gia ban 3000-6000 la: " << TimKiem(d, 0, 4);
	return 0;
}