贪心算法的应用---背包问题(easy-x图形化)

运行截图：

//贪心法求背包问题
#include<iostream>
#include<algorithm>
#include<graphics.h>
#include<conio.h>
using namespace std;
const int maxn = 1e5 + 15;
struct node {
	int p;
	int w; // 重量
	int v; // 价值
	double value; // 单位重量的价值
}a[maxn];
bool cmp(node a, node b) {
	return a.value > b.value;
}
int n;
double c;
void solve() {
	initgraph(1500, 800);
	setbkcolor(WHITE);
	cleardevice();
	setlinecolor(BLACK);
	setlinestyle(10);
	for (int i = 0; i < 5; i++) {
		int x = 0, x1 = (n + 2) * 50;
		int y = i * 30, y1 = i * 30;
		line(x, y, x1, y1);
	}
	for (int i = 0; i <= n + 2; i++) {
		if (i == 1)
			continue;
		int x = i * 50, x1 = i * 50;
		int y = 0, y1 = 4 * 30;
		line(x, y, x1, y1);
	}
	settextcolor(RED);
	for (int i = 1; i <= n; i++) {
		int x = 60 + i * 50;
		int y = 10;
		TCHAR s[2];
		_stprintf(s, _T("%d"), i);
		outtextxy(x, y, s);
	}
	for (int i = 0; i < 3; i++) {
		int x = 20;
		int y = 40 + i * 30;
		if (i == 0) {
			TCHAR s[] = _T("物品重量");
			outtextxy(x, y, s);
			for (int j = 0; j < n; j++) {
				TCHAR s1[5];
				int x1 = 120 + j * 50;
				_stprintf(s1, _T("%d"), a[j].w);
				outtextxy(x1, y, s1);
			}
		}
		if (i == 1) {
			TCHAR s[] = _T("物品总价");
			outtextxy(x, y, s);
			for (int j = 0; j < n; j++) {
				TCHAR s1[5];
				int x1 = 120 + j * 50;
				_stprintf(s1, _T("%d"), a[j].v);
				outtextxy(x1, y, s1);
			}
		}
		if (i == 2) {
			TCHAR s[] = _T("物品单价");
			outtextxy(x, y, s);
			for (int j = 0; j < n; j++) {
				TCHAR s1[5];
				int x1 = 110 + j * 50;
				_stprintf(s1, _T("%.2lf"), a[j].value);
				outtextxy(x1, y, s1);
			}
		}
	}
	sort(a, a + n, cmp);
	//贪心求解
	double res = 0;
	int t = 0;
	for (int i = 0; i < n; i++) {
		if (c >= a[i].w) {
			res += a[i].v;
			c -= a[i].w;
			int y = 4 * 30 + 20 + t * 30;
			int x = 20;
			TCHAR s[] = _T("物品 ");
			outtextxy(x, y, s);
			_TCHAR s1[3];
			_stprintf(s1, _T("%d"), a[i].p);
			outtextxy(x + 40, y, s1);
			TCHAR s2[] = _T("可以拿（重量）：");
			outtextxy(x + 55, y, s2);
			_TCHAR s3[5];
			_stprintf(s3, _T("%d"), a[i].w);
			outtextxy(x + 200, y, s3);
			t++;
		}
		else {
			res += c * a[i].value;
			//c = 0;
			int y = 4 * 30 + 20 + t * 30;
			int x = 20;
			TCHAR s[] = _T("物品 ");
			outtextxy(x, y, s);
			_TCHAR s1[3];
			_stprintf(s1, _T("%d"), a[i].p);
			outtextxy(x + 40, y, s1);
			TCHAR s2[] = _T("可以拿（重量）：");
			outtextxy(x + 55, y, s2);
			_TCHAR s3[5];
			_stprintf(s3, _T("%.2lf"), c);
			outtextxy(x + 200, y, s3);
			c = 0;
			t++;
		}
	}
	int y = 4 * 30 + 20 + t * 30;
	int x = 20;
	TCHAR s[] = _T("背包中物品的最大价值为:");
	outtextxy(x, y, s);
	_TCHAR s3[5];
	_stprintf(s3, _T("%.2lf"), res);
	outtextxy(x + 200, y, s3);
	_getch();
}
int main()
{
	cout << "请输入背包大小和物品个数：" << endl;
	cin >> c >> n;
	cout << "请输入物品的重量和价值：" << endl;
	for (int i = 0; i < n; i++) {
		cin >> a[i].w >> a[i].v;
		a[i].p = i + 1;
		a[i].value = double(a[i].v) / double(a[i].w);
	}
	solve();
	return 0;
}