动态规划问题------ 0-1背包(easy-x图形化)

运行截图：

//动态规划求0-1背包问题
#include<iostream>
#include<vector>
#include<graphics.h>
#include<conio.h>

using namespace std;

struct KNAP
{
	int w; //weight;
	int v; //value;
};

//一维的方式
void solveKPd_re(vector<KNAP> cknap, vector<int>& f, int n, int Tw)
{
	initgraph(1500, 800);
	setbkcolor(WHITE);
	cleardevice();
	setlinecolor(BLACK);
	setlinestyle(10);
	for (int i = 0; i < n + 2; i++) {
		int x = 0, x1 = (Tw + 2) * 50;
		int y = i * 30, y1 = i * 30;
		line(x, y, x1, y1);
	}

	for (int i = 0; i < Tw + 3; i++) {
		int x = i * 50, x1 = i * 50;
		int y = 0, y1 = (n + 1) * 30;
		line(x, y, x1, y1);
	}

	settextcolor(RED);
	for (int i = 0; i <= Tw; i++) {
		int x = 60 + i * 50;
		int y = 10;
		TCHAR s[2];
		_stprintf(s, _T("%d"), Tw - i);
		outtextxy(x, y, s);
	}

	for (int i = 0; i < n; i++) {
		int x = 20;
		int y = 40 + i * 30;
		TCHAR s[2];
		_stprintf(s, _T("%d"), i);
		outtextxy(x, y, s);
	}

	settextcolor(BLACK);
	for (int i = 0; i < n; i++){
		int t = 0;
		for (int j = Tw; j >= cknap[i].w; j--) {
			int x1 = 60 + t * 50;
			int y1 = 40 + i * 30;
			TCHAR s1[3];
			if (f[j - cknap[i].w] + cknap[i].v > f[j])
				f[j] = f[j - cknap[i].w] + cknap[i].v;
			_stprintf(s1, _T("%d"), f[j]);
			outtextxy(x1, y1, s1);
			t++;
		}
	}

	int x = 30;
	int y = (n + 2) * 30;
	TCHAR s[] = _T("最终的数组为：");
	outtextxy(x, y, s);
	int t = 0;
	for (int j = Tw; j >= 0; j--) {
		int x1 = 30 + t * 30;
		int y1 = (n + 3) * 30;
		TCHAR s1[3];
		_stprintf(s1, _T("%d"), f[j]);
		outtextxy(x1, y1, s1);
		t++;
	}
	int x1 = 30;
	int y1 = (n + 4) * 30;
	TCHAR s1[] = _T("最终背包获取的最大有效价值为：");
	outtextxy(x1, y1, s1);
	x1 = 300;
	TCHAR s2[3];
	_stprintf(s2, _T("%d"), f[Tw]);
	outtextxy(x1, y1, s2);
	_getch();
}

int main()
{
	cout << "请输入背包大小和物品个数：" << endl;
	int Tw; int n;
	cin >> Tw >> n;
	vector<KNAP> cknap;
	cout << "请输入物品的体积和价值: " << endl;
	for (int i = 0; i < n; i++) {
		KNAP temp;
		cin >> temp.w >> temp.v;
		cknap.push_back(temp);
	}

	vector<int> f(Tw + 1, 0);
	solveKPd_re(cknap, f, n, Tw);
	return 0;
}