Home > 算法研究 > [算法]简单的背包问题递归解法,C语言实现

[算法]简单的背包问题递归解法,C语言实现

今天讲点简单的算法,最简单的背包0算法,使用了递归的方法,相信看完代码的朋友会发现这段代码很熟悉,不过CG提供这些代码的目的只是让全部背包算法的完整提供地给大家,代码很简单,相信高手一看就懂,这里的背包算法只是考虑了物品的重量,没有考虑物品的价值,是初学递归算法的朋友必看的代码,高手的话全当复习一下吧。
因为CG最近要考试了,一口气要考6门,所以博客更新没有这么快了,请大家见谅不过我还是会保持每天提供至少一篇的速度写博文,希望大家能支持,谢谢
预告下明天的算法博文,《银行家算法》,今天复习了下操作系统,晚上重新安装了系统,浪费了两个小时,代码明天调试后奉上,希望大家继续关注。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*简单的背包问题递归解
*code CG 2009-01-04
*/
#include"stdio.h"
#define N 6 /*物品数量*/
#define S 15 /*背包大小*/
 
int W[N+1]={0,1,2,3,4,5,6};/*测试数据,各物品重量,W[0]不使用*/
 
/*knapsack()背包函数
参数	int s 剩余重量
		int n 剩余物品数
返回	int 背包分配是否成功
*/
int knapsack(int s,int n){
	if(s == 0)/*分配结束,成功*/
		return 1;
	if(s < 0 || (s > 0 && n < 1))/*没有可用空间,或者物品分配完毕*/
		return 0;
	if( knapsack(s - W[n] , n - 1)){/*递归*/
		printf("%-4d",W[n]);	/*输出*/
		return 1;
	}
return knapsack(s , n - 1);
}
int main()
{
	if(knapsack(S , N))/*递归调用*/
		printf("nOK!n");
	else
		printf("Failed!");
	return 1;
}/*main*/
Categories: 算法研究 Tags: ,
  1. January 4th, 2009 at 23:09 | #1

    呵呵支持基础算法!
    对新手帮助很大!
    现在很多学程序的新手都不好好的学习基础算法了!
    其实这些基础很关键的!

  2. January 4th, 2009 at 23:27 | #2

    有段时间没看C语言拉,大二学的,现在大三拉,哎,就要毕业落!

  3. March 27th, 2009 at 15:48 | #3

    现在很多学程序的新手都不好好的学习基础算法了
    其实这些基础很关键的,但是有时候也难懂

  4. March 27th, 2009 at 16:32 | #4

    呵呵,CG是有段时间没有静心研究研究算法放面的内容了,一有东西,马上奉上

  5. October 14th, 2009 at 22:29 | #5

    看了你的算法,觉得离C语言有点远了,看来还是得回去看看了

  6. October 14th, 2009 at 22:30 | #6

    评论咋都不审核一下

  7. August 7th, 2012 at 09:50 | #7

    背包问题 要有每件物品的价值,我不知道你写的是什么东西

  1. No trackbacks yet.