| « | August 2025 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | | | | | 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 | | | | | | | |
|
| 公告 |
本站技术贴除标明为“原创”的之外，其余均为网上转载，文中我会尽量保留原作者姓名，若有侵权请与我联系，我将第一时间做出修改。谢谢！
——既瑜 |
| 统计 |
blog名称:★既瑜★
日志总数:183
评论数量:636
留言数量:-25
访问次数:1406274
建立时间:2005年3月12日 |
OICQ：215768265
njucs2001@hotmail.com
erichoo1982@gmail.com |
|
W3CHINA Blog首页 管理页面 写新日志 退出
 [【技术文档】]算法连载（1）--贪心法之背包问题[转载] |
贪心方法：总是对当前的问题作最好的选择，也就是局部寻优。最后得到整体最优。
应用：1：该问题可以通过“局部寻优”逐步过渡到“整体最优”。贪心选择性质与“动态规划”的主要差别。
2：最优子结构性质：某个问题的整体最优解包含了“子”问题的最优解。
代码如下：
#include <iostream.h>
struct goodinfo{ float p; //物品效益 float w; //物品重量 float X; //物品该放的数量 int flag; //物品编号};//物品信息结构体
void Insertionsort(goodinfo goods[],int n){ int j,i; for(j=2;j<=n;j++) { goods[0]=goods[j]; i=j-1;
while (goods[0].p>goods[i].p) { goods[i+1]=goods[i]; i--; } goods[i+1]=goods[0]; }
}//按物品效益，重量比值做升序排列
void bag(goodinfo goods[],float M,int n){ float cu; int i,j; for(i=1;i<=n;i++) goods[i].X=0; cu=M; //背包剩余容量 for(i=1;i<n;i++) { if(goods[i].w>cu)//当该物品重量大与剩余容量跳出 break; goods[i].X=1; cu=cu-goods[i].w;//确定背包新的剩余容量 } if(i<=n) goods[i].X=cu/goods[i].w;//该物品所要放的量
/*按物品编号做降序排列*/ for(j=2;j<=n;j++) { goods[0]=goods[j]; i=j-1;
while (goods[0].flag<goods[i].flag) { goods[i+1]=goods[i]; i--; } goods[i+1]=goods[0]; }/////////////////////////////////////////// cout<<"最优解为:"<<endl; for(i=1;i<=n;i++) { cout<<"第"<<i<<"件物品要放:"; cout<<goods[i].X<<endl; }
}
void main(){ cout<<"|--------运用贪心法解背包问题---------|"<<endl; cout<<"|---power by zhanjiantao(028054115)---|"<<endl; cout<<"|-------------------------------------|"<<endl; int j; int n; float M; goodinfo *goods;//定义一个指针 while(j) { cout<<"请输入物品的总数量："; cin>>n; goods=new struct goodinfo [n+1];// cout<<"请输入背包的最大容量："; cin>>M; cout<<endl; int i; for(i=1;i<=n;i++) { goods[i].flag=i; cout<<"请输入第"<<i<<"件物品的重量:"; cin>>goods[i].w; cout<<"请输入第"<<i<<"件物品的效益:"; cin>>goods[i].p; goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比 cout<<endl; }
Insertionsort(goods,n); bag(goods,M,n); cout<<"press <1> to run agian"<<endl; cout<<"press <0> to exit"<<endl; cin>>j; }}
|
阅读全文(15896) | 回复(4) | 编辑 | 精华 |
| 回复:算法连载（1）--贪心法之背包问题[转载] |
|
anny(游客)发表评论于2007/5/12 15:38:07 |
請問背包問題(不是0-1背包喔)的時間複雜度是多少呢
|
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除 |
| 回复:算法连载（1）--贪心法之背包问题[转载] |
|
sherlockhua(游客)发表评论于2007/4/7 10:03:12 |
#include<stdio.h>#include<stdlib.h>#define Max 100/*定义栈结构*/typedef struct list{ int data[Max]; int top;}Seqstack;
/*定义一个用来存储结果的链表*/typedef struct List{ Seqstack result; struct List * Next;}Seqlist,*Pointer;
void Inicial_List(Pointer p){ p=(Pointer)malloc(sizeof(Seqlist)); p->Next=NULL;}
Seqstack Push_Stack(int n,Seqstack s){ s.top++; s.data[s.top]=n; return s;}int Add_Stack(Seqstack s){ int total=0,i; if(s.top>=0) { for(i=0;i<=s.top;i++) total+=s.data[i]; } else { total=0; } return total;}Seqstack Pop_Stack(Seqstack s){
printf("%d",s.data[s.top]); if(s.top>=0) s.top--; return s;}/*执行回溯操作的函数*//*参数说明：n->数的总的个数，a[]用来存放数的数组,k查找的总体积*/Pointer Query_Result(int n,int b[],int k){ int i,j; Seqstack mystack; Seqlist *newnode; Pointer r,p=NULL; Inicial_List(p); r=p; for(i=0;i<n;i++) { mystack.top=-1;
j=i; while(j<n) {
if(Add_Stack(mystack)+b[j]<k) { mystack=Push_Stack(b[j],mystack);
j++; } else if(Add_Stack(mystack)+b[j]==k) { mystack=Push_Stack(b[j],mystack); newnode=(Pointer)malloc(sizeof(Seqlist)); newnode->result=mystack; newnode->Next=NULL; r->Next=newnode; r=newnode; mystack=Pop_Stack(mystack); j++;
} else if(Add_Stack(mystack)+b[j]>k) {
j++; } }
} return p;}
void Print_List(Pointer p){ int i,j=0; p=p->Next; printf("welcome the outer\n"); if(p==NULL)printf("there no results\n"); while(p!=NULL) { j++; printf("the %d result is: ",j); for(i=0;i<=p->result.top;i++) {
printf(" %d",p->result.data[i]); } p=p->Next; printf("\n"); } printf("\n");}void Sort_Array(int b[],int n){ int i,j,temp; for(i=0;i<n;i++) { for(j=0;j<n-i;j++) { if(b[j]<b[j+1]) { temp=b[j]; b[j]=b[j+1]; b[j+1]=temp; } } }
}void main(){ int i,n,k,select,a[Max]; Pointer head; printf("******************************************\n"); printf("1 start\n2 exit\n"); scanf("%d",&select);
while(select==1) { printf("please input the total products\n"); scanf("%d",&n); printf("please input the volumn of n products\n"); for(i=0;i<n;i++) { printf("please input the %d integers",i+1); scanf("%d",&a[i]); } printf("\n"); printf("please input the volunm to put\n"); scanf("%d",&k); Sort_Array(a,n); head=Query_Result(n,a,k); Print_List(head); printf("******************************************\n"); printf("1 start\n2 exit\n"); scanf("%d",&select); }
}
|
| 个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除 |
| 回复:算法连载（1）--贪心法之背包问题[转载] |
|
newrain(游客)发表评论于2007/2/20 7:18:31 |
既然有两个部分进行排序，为什么不把他单独作为一个函数呢？
|
| 个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除 |
| 回复:算法连载（1）--贪心法之背包问题[转载] |
|
CCNU(游客)发表评论于2006/4/17 21:58:39 |
怎么证明背包问题具有贪心选择性质呀!!!
|
| 个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除 |
| 回复:算法连载（1）--贪心法之背包问题[转载] |
|
0(游客)发表评论于2006/4/17 21:57:52 |
怎么证明背包问题具有贪心选择性质呀!!!
|
| 个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除 |
| 回复:算法连载（1）--贪心法之背包问题[转载] |
应该是的，时间长了不记得了
|
| 个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除 |
| 回复:算法连载（1）--贪心法之背包问题[转载] |
|
feifei1225(游客)发表评论于2005/6/21 21:08:13 |
是完整的程序设计和算法分析吗？
|
| 个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除 |
» 1 »
|
