圣诞前夜讲点比较具有圣诞感觉的算法，背包问题算法，这里我写了经典算法和贪心算法两种解决方法，因为时间不多，所以给出的数组是已经排序的，因为贪心算法可能要用得到，经典算法因为是一个一个比较，因此排序也就没有那么重要了，可能两种算法的最终运行效果一样的，朋友们调试的时候记得修改我给出的测试数组，今天实在太忙了，贪心使用的排序算法没有写，留着以后给大家讲排序算法的时候使用吧，圣诞快乐，诸位朋友们。
背包问题：就是现在有一个容量为 PSIZE 的背包，同时又有 N 件 item，现在要求将这些 item 放入这个背包里面去，要求尽量放一定要求的 item（比如按照大小的顺序），又要求放最多的 item 或者放的 item 权值之和要最大
问题讲完，算法如下，C 语言实现，另外回溯、动态规划的算法，有时间也会写上，今天
实在太忙了，诸位朋友继续期待吧：
/* 背包问题之经典解法和贪心算法
*code cg
*2008 12 24
* 调试环境 TC ，devC++
*/
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#define N 5 /* 定义需要放的物件数量 */
#define PSIZE 150/* 定义背包大小 */
long item [N]={15,40,50,60,90};/* 初始化物件数组，贪心算法要求大小已排序 */
int freespace[N]={0};
int classic () {/* 经典算法 */
long size = PSIZE;
long used = 0;
int i;
for(i = N - 1 ; i >= 0 ; i--){
if ((size - used) >= item [i]){/* 大小可以放入吗？*/
used += item [i]; /* 放入背包 已使用数加新物件的大小 */
freespace[i] = 1;
}
else { /* 大小太大 */
freespace[i] = 0;
}
}/*for*/
return 1;
}
int greedy (){/* 贪婪算法 */
int i;
long size = PSIZE;
long used = 0;
for (i = N - 1 ; i>= 0 ; i--){/* 先放大的物体，再考虑小的物体 */
if ((used + item [i]) < = size){/* 如果当前物体可以放入 */
freespace [i] = 1;/*1 表示放入 */
used += item [i];/* 背包剩余容量减少 */
}
else{
freespace[i]=0;
}
}/*for*/
if (size == used)/* 返回 */
return 1;
else
return 0;
}
void main()
{
int i;/* 计数器 */
for(i = 0 ; i < N ; i++){
if(i % 5 == 0 )
printf("n");
printf ("%10ld" , item [i]);/* 首先输入原始数据 */
}/*for*/
printf("nClassicn");
if (classic ()==1){/* 经典算法 */
printf("Result");
for(i=0;i
printf("nGreedyn");
if (classic ()==1){/* 经典算法 */
printf("Result");
for(i=0;i