算法实验5《算法综合实验》
使用回溯法解决0-1背包问题
#include<iostream> using namespace std; int n, c, bestp; //物品的个数,背包的容量,最大价值 int p[80], w[80], x[80], bestx[80]; //物品的价值,物品的重量,x[i]暂存物品的选中情况,物品的选中情况 void Backtrack(int i, int cp, int cw) { //cw当前包内物品重量,cp当前包内物品价值 int j; if (i>n)//回溯结束 { if (cp>bestp) { bestp = cp; for (i = 0; i <= n; i++) bestx[i] = x[i]; } } else for (j = 0; j <= 1; j++) { x[i] = j; if (cw + x[i] * w[i] <= c) { cw += w[i] * x[i]; cp += p[i] * x[i]; Backtrack(i + 1, cp, cw); cw -= w[i] * x[i]; cp -= p[i] * x[i]; } } } int _tmain(int argc, _TCHAR* argv[]) { bestp = 0; cout << "输入背包最大容量,物品个数,物品的重量,物品的价值 "; cin >> c; cin >> n; for (int i = 1; i <= n; i++)cin >> w[i]; for (int i = 1; i <= n; i++)cin >> p[i]; Backtrack(1, 0, 0); cout << "最大价值为:" << bestp; printf(" 被选中的物品依次是 "); for (int i = 1; i <= n; i++)if (bestx[i])cout << "第" << i << "个物品" << endl; system("pause>nul"); return 0; }
上一篇:
IDEA上Java项目控制台中文乱码