0-1背包问题动态规划、回溯法

给定n个物品和一背包，物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？
第一行输入一个n，c，代表有n个物品背包容量为c
接下来n行，每行输入wi，和vi
其中0 输入 
4 8
2 3
3 4
4 5
5 6
输出
10

目录

一、动态规划法

二、回溯法

一、动态规划法

分析：动态规划的核心是找到状态转移方程，0-1背包问题思考的是第i个物品装与不装的问题，需要比较装和不装那个价值更大,我们用n行从列的矩阵存储价值

1、子问题:m(i,j)的问题，即有j容量可选择i个物品装入的问题

2、对于j 容量我们需要考虑装不装得下第i个物品，若装不下m[i][j]=m[i-1][j],0

3、状态转移方程：w[i]& & \ m[i-1][j],0

代码实现：

#include
int m[100][100];//前i个物品装入容量为j的背包中获得的最大价值
int max(int a,int b){//找最大值函数 
	if(a>=b) return a;
	return b;
}
int Ksnap(int n,int w[],int v[],int c){//用n行c列的矩阵存储价值 
	//初始化第一行第一列为0 
	for(int i=0;i<=n;i++){
		m[i][0]=0;
	}
	for(int i=0;i<=c;i++){
		m[0][i]=0;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=c;j++){
			if(j 
二、回溯法 
分析：0-1背包问题的解空间可以用子集树表示。解0-1背包问题的回溯法与解装载问题的回溯法十分相似 
 在搜索解空间树时，只要其左儿子节点是一个可行的节点，搜索就进入其左子树;
 而当右子树中有可能包含最优解时才进入右子树搜索，否则将右子树剪去
 设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+r<=bestp时，可剪去右子树
 对于0-1背包问题，可用一颗完全二叉树表示其解空间
 
#include
#define N 100
int n,c;
int w[N],v[N];
int sum=0,bestsum=0,wp=0;//定义当前价值和，当前最优价值和，当前背包内物品重量
//设置标志位，标志进入左右分支
int x[N];

void backtrack(int i){//i表示第i个物品
	if(i>=n){//到了n个物品 
		if(bestsum