引入：货币种类25 、20、5、1分四种，现在找零41分钱，要求找零正确，并且用的零钱数目最少
分析问题：
1、分解子问题，确定最优解的策略
用脑子想想具体的情境：每次找零的动作就是一个子问题。在找零时，你会怎么考虑？是不是每次尽量先用最大的钱，应该明白正常人不会找一堆一分的硬币给顾客
2、用局部最优解堆叠出全局最优解
<span style="font-size:24px;">#include<stdio.h>
static int yingB[4]={25,20,5,1};//这里为了方便直接用了递减序
int main ()
{
int sum,temp=0;//temp是当前积累的钱数
int i=0;
printf("输入要找零的总钱数：\t");
scanf("%d",&sum);
printf("\n");
while(i<4)
{
if(temp<sum)
{
temp+=yingB[i];
printf("+%d",yingB[i]);
}
if(temp>sum)
{
temp-=yingB[i];rintf("-%d",yingB[i]);
i=i+1;
}
if(temp==sum) break;
}
printf("= %d\n",sum);
return 0;
}</span>
最后的结果是：一个25 三个5 一个1
/*在运行窗口的结果如下*/
输入要找零的总钱数： 41+25+25-25+20-20+5+5+5+5-5+1= 41然而聪明的人毕竟比机器机智，41=20*2+1，明明只需要三个不就搞定了！这正是贪婪法自身的特性所决定的：我追求的是接近于最优解，但不一定是最优解。但是也不能就此轻视他，有时候做到完美不过是浪费时间，不是吗？
正题：01背包问题
要到一个荒岛体验生活，现在我可以带一个背包装我需要的东西，假设这些东西都不相同，且只有一个（那就是只有两种情况：带走1、不带0）;每件物品都有自身的重量和价值
<span style="font-size:24px;">物品列表 重量（kg） 35 30 60 50 40 10 25 价值（千元） 10 40 30 50 35 40 30 价值密度 0.3 1.3 0.5 1 0.875 4 1.2 (千元/kg</span>)
这个问题的子问题也是按步骤分，放入的顺序就是你的最优策略：在这里有三种方式，每次放最轻的、价值最大的、价值密度最大的。
现在问题已经十分清晰了，再有就是看你的编程语言的表达能力的强弱，会不会把自己的想法用代码表达出来。
/<span style="font-size:24px;">*背包问题----贪婪法：用自己的最优解模型将子问题的最优解堆叠得出全局最优解*/
//算法分析
/*1、制定策略（按最轻的、按最有价值的，按价值密度）*/
/*2、根据策略依次找到合适的序号（物品）*/
/*3、加入背包，并判定背包的承重*/
/*4、对已经加入的物品更改状态*/
/*5、记录放入背包的物品，同时输出*/
/*物品重量 35 30 60 50 40 10 25*/
/*物品价值 10 40 30 50 35 40 30*/
/*背包承重 150*/
#include<stdio.h>
#include<stdlib.h>
typedef struct tagObject{
int weight;
int price;
int status;
}OBJECT;
typedef struct tagKnapsackProblem{
int totalC;
OBJECT objs[7];
}KNAPSACK_PROBLEM;
int choosefun1(OBJECT objs[],int c)//c是当前的背包剩余重量
{
int index =-1;
int maxprice=0;
for(int i=0;i<7;i++)
{
if((objs[i].status==0)&&(objs[i].price>maxprice))
{
maxprice=objs[i].price;
index=i;
}
}
return index;//返回价值最大的物品序号
}
void GreedyAlog(KNAPSACK_PROBLEM *problem)
{
int idx;
int ntc=0;
while((idx=choosefun1(problem->objs,problem->totalC-ntc))!=-1)
{
if((ntc+problem->objs[idx].weight)<=problem->totalC)
{
problem->objs[idx].status=1;
ntc+=problem->objs[idx].weight;
printf("已装入第%d件\t",idx+1);
}
else
{
problem->objs[idx].status=2;
}
}
return;
}
int main ()
{
KNAPSACK_PROBLEM *problem=(KNAPSACK_PROBLEM *)malloc(sizeof(KNAPSACK_PROBLEM));
printf("请输入七件物品每一件的重量 价格(之间用空格隔开）:\n");
for(int i=0;i<7;i++)
{
printf("第%d件: ",i+1);
scanf("%d %d",&problem->objs[i].weight,&problem->objs[i].price);
problem->objs[i].status=0;
}
printf("请输入背包的承重最大值：\n");
scanf("%d",&problem->totalC);
GreedyAlog(problem);
free(problem);
printf("\n");
return 0;
}</span>
当然，如果使用宏定义物品数，最好编写一个输入函数，让主程序更简洁。