软件工程

本类阅读TOP10

·PHP4 + MYSQL + APACHE 在 WIN 系统下的安装、配置
·Linux 入门常用命令(1)
·Linux 入门常用命令(2)
·使用 DCPROMO/FORCEREMOVAL 命令强制将 Active Directory 域控制器降级
·DirectShow学习(八): CBaseRender类及相应Pin类的源代码分析
·基于ICE方式SIP信令穿透Symmetric NAT技术研究
·Windows 2003网络负载均衡的实现
·一网打尽Win十四种系统故障解决方法
·数百种 Windows 软件的免费替代品列表
·收藏---行百里半九十

分类导航
VC语言Delphi
VB语言ASP
PerlJava
Script数据库
其他语言游戏开发
文件格式网站制作
软件工程.NET开发
背包问题另解

作者:未知 来源:月光软件站 加入时间:2005-2-28 月光软件站

背包问题:有不同价值,不同重量的物品n件,求这 件物品中选取一部分,
是选中物品的总重量不超过指定的限制重量,但选取的物品总价值要最大。


解题思想:利用递归求出所选取的物品的所有可能,将满足限制重量条件的进行复值,
Value始终存放最大的物品总价值,Weight是满足条件的物品的总重量,以下
是我自己写的一段代码,与《系统设计师》教程中的思路是不一样的,代码
经过编译的,而且运行结果正确:
 
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
struct Bag
{ int weight;
  int value;
}Bag[MAX];
int a[MAX];
int Value=0;
int Weight;
int comb(int m,int k)
{int i,j;
 int wei,val;
 for(i=m;i>=k;i--)
   { a[k]=i;
     if(k>1)
  comb(i-1,k-1);
     else
       { wei=0;                                //预值0
  val=0;
  for(j=a[0];j>0;j--)                  //每一种组合求它们的重量和价值
     { wei=wei+Bag[a[j]].weight;
       val=val+Bag[a[j]].value;
     }
  if(wei<=Weight&&val>Value)          //判断是否满足条件进行附值
     Value=val;
       }
    }
 return Value;
 }
void main()
{ int num,subnum;
  int l,
  clrscr();
  printf("\nenter the number of total Bag:"); //输入背包的总个数
  scanf("%d",&num);
  printf("\nenter %d number Bag'weight and Bag'value(sample *,* )\n",num);  //输入背包的重量和价值
  for(l=1;l<=num;l++)
      scanf("%d,%d",&Bag[l].weight,&Bag[l].value);
  printf("\nenter the subnumber of the Bag:");                             //输入要求背包的个数
  scanf("%d",&subnum);
  printf("\nenter the Weight for %d Bag:",subnum);                         //输入满足条件的重量
  scanf("%d",&Weight);
  a[0]=subnum;
  printf("\nthe max value is:%d",comb(num,subnum));
  getch();
}
总结:在看参考书的例子的时候,应该多动脑筋先想一想。再进行比较,对自己有很大帮助。




相关文章

相关软件