01背包的两种简单的实现方法（递归）（递推）（c语言）

目录

前言

准备工作

递归法

递推法

 最后

前言

        本文较为基础，会涉及到动态规划的内容,也就是Dynamic Programming。看不懂的小伙伴可以先去找找视频或图解，先搞明白该思想是想干一件什么样的事，再去试着理解该思想在程序层面是怎么实现的，或许会比较好入门。

准备工作

        已经学过指针，数组以及基本的控制语句。

递归法

（让我们来看看代码吧）

#include

#define max(a,b) (a>b?a:b)    

int v[1001],w[1001];        //    用来存储每个东西的价格和重量
int rec( int i, int j,int n)
{
	int res;
	if ( i==n ){
            //已经没东西了
		res = 0;
	}else if ( j < w[i] ){
            //单单这个东西的重量就无法放进背包，于是跳过它
		res = rec( i+1 ,j,n);       
	}else {
            //比较加入这个东西后和没加时的价值
		res = max(rec(i+1,j,n),rec(i+1,j-w[i],n)+v[i]);    //难点
	}
	return res;
}

int main()
{
	static int n,W;		//W代表最大拿多少重的东西  n代表有多少个东西 
	scanf("%d%d",&W,&n);
	

	for (int i=0;i 
 
         难点在于怎么理解rec这个函数的不断调用，也就是 
 
       
 
res = max(rec(i+1,j,n),rec(i+1,j-w[i],n)+v[i]);    
 
        在这个地方rec自己调用了自己两次，于是就像一根往下生长的根一样，越往下，同一层分叉的根越多。
 
 
递推法 
        （以下是代码）
 
        
 
#include

#define max(a,b) (a>b?a:b)

int main()
{
	int n,W;		//W代表最大拿多少重的东西  n代表有多少个东西 
	int i,j;
	int dp[100][100]={{0}};        //一个记忆数组，像是在画一个表格一样
	int w[100],v[100];             //存储对应的重量和价格的数组
	
    scanf("%d%d",&W,&n);           //输入最多可拿多重的东西和一共有多少个东西
	

	for ( i=0;i 
         这里实现的思路：我们画一个表格，每个格子内都是处在那个重量的条件下的最优解。如（n,W）表示当轮到第n个东西，且最重只能拿W时，所能拿的最大价值是多少。
 
        
 
 
 
 最后 
        其实01背包还有几个比较的方法解决，由于时间问题，后续应该会补上。
 
        （碍于作者水平有限，若是盆友们发现问题，还请斧正）