用递归方法求解0/1背包问题

深入掌握递归算法设计方法

#include
#define MaxSize 100
int pathnum（int mint n）
{
	if （m<1||n<1）return 0;
	if （m==1&&n==1）;
	return pathnum（m-1n）+pathnum（mn-1）;
}
typedef struct
{
	int ij;
}PathType;
int count=0;
void disppath（int mint nPathType path[]int d）
{
	if （m<1||n<1）return;
	if （m==1&&n==1）
	{
		d++;
		path[d].i=m;
		path[d].j=n;
		printf（“路径%d:“++count）;
		for （int k=0;k<=d;k++）
			printf（“（%d%d）“path[k].ipath[k].j）;
		printf（“\n“）;
	}
	else
	{
		d++;
		path[d].i=m;
	    path[d].j=n;
		disppath（m-1npathd）;
		disppath（mn-1pathd）;
	}
}
int main（）
{
	int m=2n=5;
	printf（“m=%dn=%d的路径条数:%d\n“mnpathnum（mn））;
	PathType path[MaxSize];
	int d=-1;
	disppath（mnpathd）;
	return 1;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2019-10-10 09:14  P121 exp5_8\
     目录           0  2019-10-10 09:10  P121 exp5_8\Debug\
     文件       28160  2019-10-10 09:10  P121 exp5_8\Debug\P121 exp5_8.exe
     文件      303456  2019-10-10 09:10  P121 exp5_8\Debug\P121 exp5_8.ilk
     文件      363520  2019-10-10 09:10  P121 exp5_8\Debug\P121 exp5_8.pdb
     目录           0  2019-10-10 08:56  P121 exp5_8\ipch\
     目录           0  2019-10-10 08:56  P121 exp5_8\ipch\p121 exp5_8-30902ccc\
     文件     1441792  2019-10-10 08:56  P121 exp5_8\ipch\p121 exp5_8-30902ccc\p121 exp5_8-e31062e9.ipch
     目录           0  2019-10-10 09:08  P121 exp5_8\P121 exp5_8\
     文件         684  2019-10-10 09:13  P121 exp5_8\P121 exp5_8\02.cpp
     目录           0  2019-10-10 09:10  P121 exp5_8\P121 exp5_8\Debug\
     文件        8424  2019-10-10 09:10  P121 exp5_8\P121 exp5_8\Debug\02.obj
     文件         728  2019-10-10 09:08  P121 exp5_8\P121 exp5_8\Debug\cl.command.1.tlog
     文件        1646  2019-10-10 09:08  P121 exp5_8\P121 exp5_8\Debug\CL.read.1.tlog
     文件         592  2019-10-10 09:08  P121 exp5_8\P121 exp5_8\Debug\CL.write.1.tlog
     文件        1530  2019-10-10 09:10  P121 exp5_8\P121 exp5_8\Debug\link.command.1.tlog
     文件        3038  2019-10-10 09:10  P121 exp5_8\P121 exp5_8\Debug\link.read.1.tlog
     文件        1038  2019-10-10 09:10  P121 exp5_8\P121 exp5_8\Debug\link.write.1.tlog
     文件         644  2019-10-10 09:10  P121 exp5_8\P121 exp5_8\Debug\mt.command.1.tlog
     文件         828  2019-10-10 09:10  P121 exp5_8\P121 exp5_8\Debug\mt.read.1.tlog
     文件         456  2019-10-10 09:10  P121 exp5_8\P121 exp5_8\Debug\mt.write.1.tlog
     文件         381  2019-10-10 09:10  P121 exp5_8\P121 exp5_8\Debug\P121 exp5_8.exe.intermediate.manifest
     文件         100  2019-10-10 09:10  P121 exp5_8\P121 exp5_8\Debug\P121 exp5_8.lastbuildstate
     文件        2152  2019-10-10 09:10  P121 exp5_8\P121 exp5_8\Debug\P121 exp5_8.log
     文件         713  2019-10-10 09:08  P121 exp5_8\P121 exp5_8\Debug\P121 exp5_8.vcxprojResolveAssemblyReference.cache
     文件           0  2019-10-10 09:08  P121 exp5_8\P121 exp5_8\Debug\P121 exp5_8.write.1.tlog
     文件       35840  2019-10-10 09:10  P121 exp5_8\P121 exp5_8\Debug\vc100.idb
     文件       61440  2019-10-10 09:10  P121 exp5_8\P121 exp5_8\Debug\vc100.pdb
     文件        3222  2019-10-10 09:08  P121 exp5_8\P121 exp5_8\P121 exp5_8.vcxproj
     文件         940  2019-10-10 09:08  P121 exp5_8\P121 exp5_8\P121 exp5_8.vcxproj.filters
     文件         143  2019-10-10 08:55  P121 exp5_8\P121 exp5_8\P121 exp5_8.vcxproj.user
............此处省略72个文件信息