haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 初中作文初中作文

回溯

发布时间:2013-12-18 12:31:20  

#include<stdio.h>
int main()
{
int w[50],p[50],a[50],b[50],c;
int i,j,n,g,o,m;
printf("请输入物品数 N:");
scanf("%d",&n);
printf("请输入背包容量 C:");
scanf("%d",&c);
for(i=1;i<=n;i++)
{
printf("第%d件物品w[%d],p[%d]:",i,i,i);
scanf("%d%d",&w[i],&p[i]);

}
for(i=0;i<50;i++)
{a[i]=0;b[i]=0;}
m=0;o=0;
int k,s=0;
i=1;a[i]=1;
while(1)
{
g=1;
for(k=i-1;k>=1;k--)
if(a[i]==a[k])g=0;
int l=m;
if(g==1&&c>l+w[a[i]])
{m+=w[a[i]];o+=p[a[i]];}
if(s<o)
{
s=o;
for(j=1;j<=i;j++)
b[j]=w[a[j]];
b[0]=i;
}
if(l+w[a[i]]<c&&g){i++;a[i]=a[i-1];continue;}
while(i>1&&a[i]==n){i--;m-=w[a[i]];o-=p[a[i]];l-=w[a[i]];}
if(a[i]==n&&i==1)break;
else a[i]=a[i]+1;
}
printf("最优决解方案:");
for(i=1;i<=b[0];i++)printf("%d ",b[i]);
printf("\n");
printf("总价值:%d\n",s);
}

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com