1 / 8
文档名称:

算法设计-0-1背包问题用动态规划的递归实现与非递归实现(共8页).doc

格式:doc   大小:43KB   页数:8页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

算法设计-0-1背包问题用动态规划的递归实现与非递归实现(共8页).doc

上传人:gxngqvk 2022/2/23 文件大小:43 KB

下载得到文件列表

算法设计-0-1背包问题用动态规划的递归实现与非递归实现(共8页).doc

文档介绍

文档介绍:精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
华南农业大学
过本次实验,让我意识到我对编程的不足,但也了解到自己的成长空间还很大。

附录:源代码
递归实现:
#include <>
#define N 100 //最大物品总种数
int n;//物品总种数
float limitW;//限制的总重量
float totV;//全部物品的总价值
float maxv;//解的总价值
int option[N];//解的选择
int cop[N];//当前解的选择
struct {//物品结构
float weight;
float value;
}a[N];
void find(int i,float tw,float tv)
{
int k;
//物品i包含在当前方案的可能性
if(tw+a[i].weight <= limitW)
{
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
cop[i]=1;
if(i<n-1)
find(i+1,tw+a[i].weight,tv);
else
{
for(k=0;k<n;++k)
option[k]=cop[k];
maxv=tv;
}
}
cop[i]=0;
//物品i不包含在当前方案的可能性
if(tv-a[i].value>maxv)
{
if(i<n-1)
find(i+1,tw,tv-a[i].value);
else{
for(k=0;k<n;++k)
option[k]=cop[k];
maxv=tv-a[i].value;
}
}
}
int main()
{
int k;
float w,v;
printf("输入物品种数:");
scanf("%d",&n);
printf("输入各物品的重量:");
for(k=0;k<n;++k){
scanf("%f",&w);
a[k].weight = w;
}
printf("输入各物品的价值:");
for(totV=,k=0;k<n;++k){
scanf("%f",&v);
a[k].value = v;
totV += v;
}
printf("输入限制重量:");
scanf("%f",&limitW);
maxv=;
for(k=0;k<n;++k)cop[k]=0;
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
find(0,,totV);
printf("选择的物品:");
for(k=0;k<n;++k)
printf("%d",option[k]);
printf("\