Cái túi (Xếp ba lô)

// xay dung code giai bai toan xep ba lo hay bai toan cai tui
// Khai bao cac ham thu vien neu co
#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
// Xay dung struct nhu sau
struct MONDO
{
	unsigned w; //trong luong món do
	int v; //giá tri món do
	unsigned n; //so luong món do
};
//Khai báo bien toàn cuc
MONDO a[100];
int n;//so loai món do khác nhau
//doc du lieu tu tap tin file
void ifp(char *fname, MONDO a[], int &n)
{
	ifstream fp;
	fp.open("nhap.txt");
	if (!fp)exit(1);
	else
	{
		int i;
		fp >> n;
		for (i = 0; i < n; i++)
		fp >> a[i].w;
		for (i = 0; i < n; i++)
		fp >> a[i].v;
		for (i = 0; i < n; i++)
		fp >> a[i].n;
	}
}
//
void swp(MONDO &a, MONDO &b)
{
	MONDO tmp = a;
	a = b;
	b = tmp;
}
// sap xep mon do giam dan theo don gia
void sort(MONDO a[], int n)
{
	for (int i = 0; i<n - 1; i++)
	for (int j = i + 1; j<n; j++)
	if (a[i].v*1.0 / a[i].w < a[j].v*1.0 / a[j].w)
	swp(a[i], a[j]);
}
//sap xep mon do giam dan theo gia tri
void sort2(MONDO a[], int n)
{
	for (int i = 0; i<n - 1; i++)
	for (int j = i + 1; j<n; j++)
	if (a[i].v < a[j].v)
	swp(a[i], a[j]);
}
// Xep mon do tang dan theo trong luong
void sort3(MONDO a[], int n)
{
	for (int i = 0; i<n - 1; i++)
	for (int j = i + 1; j<n; j++)
	if (a[i].w > a[j].w)
	swp(a[i], a[j]);
}
// su dung thuat toan tham lam de giai bai nay
int greedy(MONDO a[], int n,MONDO chon[], int &nc,unsigned c)
{

	sort2(a, n);
	int tong = 0, i;
	nc = 0;
	do {
	i = 0;

	while (i < n && a[i].w>c || a[i].n == 0)
		i++;
	if (i < n)
	{
	chon[nc++] = a[i];
	c -= a[i].w;
	tong += a[i].v;
	a[i].n--;
	}
	} while (i < n);
	return tong;
}
//xuat so luong
void opn(MONDO a[], int n)
{
	cout << "number: ";
	for (int i = 0; i < n; i++)
	cout << setw(3) << a[i].n;
	cout << endl;
}
//xuat trong luong
void opw(MONDO a[], int n)
{
	cout << "weight: ";
	for (int i = 0; i < n; i++)
	cout << setw(3) << a[i].w;
	cout << endl;
}
// Xuat gia tri
void opv(MONDO a[], int n)
{
	cout << "value : ";
	for (int i = 0; i < n; i++)
	cout << setw(3) << a[i].v;
	cout << endl;
}
// Xuat ket qua
void inkq(MONDO c[], int n)
{
	int i;
	for (i = 0; i<n; i++)
	{
		cout << "[" << setw(2) << c[i].w << "," << setw(2) << c[i].v <<
		"]" << endl;
	}
}
// Chuong trinh chinh
int main()
{
	MONDO chon[100];
	int nc, max;
	ifp("ip.txt", a, n);
	opw(a, n);
	opv(a, n);
	opn(a, n);
	max = greedy(a, n, chon, nc, 37);
	cout << endl << "Danh sach cac mon hang:" << endl;
	inkq(chon, nc);
	cout << "Tong cac gia tri mon hang lay duoc: " << max << endl;
	return 0;
}
// tao 1 file .txt nhu sau