一个过，不过习惯了。因为昨天打篮球了，打得好爽啊!!所以今天早上累得不 睡到十点多，睡得也很爽!!
第一个电话竟是邮局打的，家里寄的“函调”到了。
本想去取的，可是天气不太好。就不去了。
好久没有去网吧了，就去看“肖申克的救赎”了。
真是一部很好的电影!!!
十分感人，主演是曾主演“阿甘正传”的蒂姆罗宾斯
曾经有个名导演说过“美女是成功电影的共同点”，确实荷尔蒙可以促进评委对电影的兴趣，但像“肖申克的救赎”这样的电影确实是很难得的，感情很细腻表达得也很委婉，但确实是挺感人的。
看完电影后就回来看算法了。
感觉自己对常用的算法还是不太熟悉啊。
、
、这里例一个非递归贪婪0-1背包问题吧。
#include
#define N 100
double limitW;
int cop[N]; /*临时最佳候选解的选择方案，当cop[i]为1，则物品i在解中*/
struct ele{
double weight;
double value;
}a[N];
int cop[N];
int k,n;
struct{
int flag; /*物品选中状态,0:不选, 1：选中；2：曾被选中*/
double tw;//背包中当前的重量
double tv;//背包期望的价值，，注意是期望的
}twv[N]; //当前各个物品的选中状态及当前的背包中的重量、价值的信息。
void next(int i,double tw,double tv)
{ twv[i].flag=1; twv[i].tw=tw; twv[i].tv=tv; } //设置下一个元素的信息
double findMaxv(int n,ele *a) //核心函数用非递归贪婪法找出0-1解
void main(){
double maxv;//最大价值
printf("物品总数N"); scanf("%d",&n);
printf("背包限重limitW"); scanf("%d",&limiW);
printf("输入各个物品的重量及价值");
for(int i=0;i<n;i++){
printf("输入物品i的重量");
scanf("%4f",&a[i].weight);
printf("输入物品i的价值");
scanf("%4f",&a[i].value);
}
printf("一种解");
for(int i=0;i<n;i++){
printf("物品%d",cop[i]);
}
double findMaxv(int n,ele *a) { //核心函数用非递归贪婪法找出0-1解
double totalv; //期望价值值
double tw,tv; //临时重量与价值
int f ;//临时标志
totalv=0;
for(int i=0;i<n;i++) totalv+=a[i].weight; 开始时期望价值为总价值
next(0,0.0,totalv); //初始化背包
i=0;
while(i>0){
f=twv[i].flag; tw=twv[i]; tv=twv[i].value;
swich(f){
case 1://考虑装入物品i
twv[i].flag++;
if(tw+a[i].weight<limitW){
if(i<n-1){ //物品i是否为最后一个
next(i+1,tw+a[i].weight,totalv);
i++;
}
else{
maxv=totalv;
for(k=0;k<n;k++)
cop[k]=twv[k].flag!=0;
}
break;
}
break;
case 0:
i--;break;
default:
twv[i].flag=0;
if(tv-a[i].value>maxv){
if(i<n-1){//当前物品不在考虑中
next(i+1;tw;tv);
i++;
}
else{
maxv=tv-a[i].value;
for(k=0;k<n;k++)
cop[k]=twv[k].flag!=0;
}
}
break;
}
}
}