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

res = max(rec(i+1,j,n),rec(i+1,j-w[i],n)+v[i]);    

#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