---恢复内容开始---

一.0-1背包问题

二.给定n(n<=100)种物品和一个背包。物品i的重量是wi，价值为vi，背包的容量为C(C<=1000)。问:应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。

三.代码实现

#include
     
      #include
      
       using namespace std;struct baag{	double w;	double p;}bag[200];int n, c, cw = 0, cp = 0, bestp = 0;int Bound(int t) {	int cleft = c - cw;	int b = cp;	while (t <= n && bag[t].w <= cleft) {		cleft -= bag[t].w;		b += bag[t].p;		t++;	}		if (t <= n)		b += bag[t].p * cleft / bag[t].w;			return b;} void Backtrack(int t) {	if (t > n) {		if (cp > bestp)			bestp = cp;		return;	}	else{		if (cw + bag[t].w <= c) {			cw += bag[t].w;			cp += bag[t].p;			Backtrack(t + 1);			cw -= bag[t].w;			cp -= bag[t].p;		}			if (Bound(t + 1) > bestp) {			Backtrack(t + 1);		}	}	}bool cmp(baag a, baag b) {	double ap = a.p / a.w;	double bp = b.p / b.w;	return ap > bp;}int main() {	cin >> n >> c;	for (int i = 1; i <= n; i++) {		cin >> bag[i].w >> bag[i].p;	}	sort(bag + 1, bag + n + 1, cmp);	Backtrack(1);	cout << bestp;}
      
     

　　四.通过回溯法实现0-1背包问题,在分支中进行选择,慢满足条件则继续执行,不满足则回溯到上一步选择右子树,直到满足要求输出。结对时，发现问题较难，因此采取互相讨论，再结合课本的样例，最终实现的代码。这个过程中，讨论和交流起到重要作用。