haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 幼儿教育 > 幼儿读物幼儿读物

背包问题

发布时间:2014-03-03 15:10:33  

徐州工程学院

数理学院

案例分析报告

课程名称 运筹学及应用

案例分析题目 背包问题 专 业 信息与计算科学 班 级 11调查 姓 名 张永安 学 号 20110401117 指导教师 赵建强 成绩等级

2013年 12 月 20 日

《运筹学》课程设计报告

目 录

小组成员分工………………………………………………………………………3

一.问题描述………………………………………………………………………4

二.问题分析………………………………………………………………………6

三.模型建立………………………………………………………………………7

四.模型求解与程序设计…………………………………………………………8

五.结果分析………………………………………………………………………15

- 2 - 2

- 3 - 3 《运筹学》课程设计报告 小组人员详细分工

《运筹学》课程设计报告

一.问题描述

第i种每件价值c1=65,c2=85,c3=40元; 第i种物品每件重量为:w1=2,w2=3,w3=1公斤;现有一只可装载重量为5公斤的背包,求各种物品应各取多少件放入背包,使背包中物

品的价值最高。

二.问题分析

在0/1背包问题中,物体或者被装入背包,或者不被装入背包,只有两种选择。

循环变量i,j意义:前i个物品能够装入载重量为j的背包中

(n+1)*(m+1)数组value意义:value[i][j]表示前i个物品能装入载重量为j的背包中物

品的最大价值

若w[i]>j,第i个物品不装入背包

否则,若w[i]<=j且第i个物品装入背包后的价值>value[i-1][j],则记录当前最大价值

(替换为第i个物品装入背包后的价值)

计算最大价值的动态规划算法如下:

//计算

for(i=1;i<row;i++)

{

for

(j=1;j<col;j++)

{

//w[i]>j,第i个物品不装入背包

value[i][j]=value[i-1][j];

//w[i]<=j,且第i个物品装入背包后的价值>value[i-1][j],则记录当前最大价值

int

temp=value[i-1][j-w[i]]+v[i];

if

(w[i]<=j && temp>value[i][j])

value[i][j]=temp;

}

- 4 - 4

《运筹学》课程设计报告

}

即该段程序完成以下n个阶段:

1:只装入1个物品,确定在各种不同载重量的背包下,能够得到的最大价值 2:装入2个物品,确定在各种不同载重量的背包下,能够得到的最大价值

。。。

n:以此类推,装入n个物品,确定在各种不同载重量的背包下,能够得到的最大价值

三.模型建立

确定装入背包的具体物品,从value[n][m]向前逆推:

若value[n][m]>value[n-1][m],则第n个物品被装入背包,且前n-1个物品被装入载

重量为m-w[n]的背包中

否则,第n个物品没有装入背包,且前n-1个物品被装入载重量为m的背包中

以此类推,直到确定第一个物品是否被装入背包为止。逆推代码如下:

//逆推求装入的物品

j=m;

for(i=row-1;i>0;i--)

{

if

(value[i][j]>value[i-1][j])

{

c[i]=1;

j-=w[i]; }

}

四.模型求解与程序设计

输入数据及输出数据均在文件中。

- 5 - 5

《运筹学》课程设计报告

输入数据格式:

n m

w1 w2 ... wn

v1 v2 ... vn

输出数据格式:

maxValue

i count //i表示物品编号,count表示该物品被选中次数

...

/************************************************************************

* 0/1背包问题求解

(visual studio 2005)

* 给定一个载重量为m,及n个物品,其重量为wi,价值为

vi,1<=i<=n

* 要求:把物品装入背包,并使包内物品价值最大

************************************************************************/

#include <stdio.h>

#include <stdlib.h>

#include <string

.h>

#define

FILENAMELENGTH 100

class CBeibao

{

public

:

int m_nNumber; //物品数量

int m_nMaxWeight; //最大载重量

int *m_pWeight; //每个物品的重量

int *m_pValue; //每个物品的价值

int *m_pCount; //每个物品被选中的次数

int m_nMaxValue; //最大价值

public

:

CBeibao(const char

*filename);

~CBeibao();

- 6 - 6

《运筹学》课程设计报告

int

GetMaxValue();

int GetMaxValue(int n,int m,int *w,int *v,int

*c);

void Display(int

nMaxValue);

void Display(int nMaxValue,const char *filename);

};

//读入数据

CBeibao::CBeibao(const char *filename)

{

FILE *fp=fopen(filename,"r");

if

(fp==NULL)

{

printf("can not open file!");

return;

//exit(0);

}

//读入物品数量和最大载重量

fscanf(fp,"%d%d",&m_nNumber,&m_nMaxWeight);

m_pWeight=new int

[m_nNumber+1];

m_pValue=new int

[m_nNumber+1];

m_pWeight[0]=0;

//读入每个物品的重量

for(int

i=1;i<=m_nNumber;i++)

fscanf(fp,"%d",m_pWeight+i);

m_pValue[0]=0;

//读入每个物品的价值

for(int

i=1;i<=m_nNumber;i++)

fscanf(fp,"%d",m_pValue+i);

//初始化每个物品被选中次数为

m_pCount=new int

[m_nNumber+1];

for(int

i=0;i<=m_nNumber;i++)

m_pCount[i]=0;

- 7 -

7

《运筹学》课程设计报告

fclose(fp);

}

CBeibao::~CBeibao()

{

delete[] m_pWeight;

m_pWeight=NULL;

delete[] m_pValue;

m_pValue=NULL;

delete[] m_pCount; m_pCount=NULL;

}

/************************************************************************

* 动态规划求出满足最大载重量的最大价值

* 参数说明:n:物品个数

* m:背包载重量

* w:重量数组

* v:价值数组

* c:是否被选中数组

* 返回值:最大价值

************************************************************************/

int CBeibao::GetMaxValue(int n,int m,int *w,int *v,int *c)

{

int

row=n+1;

int

col=m+1;

int i,j; //循环变量:前i个物品能够装入载重量为j的背包中

//value[i][j]表示前i个物品能装入载重量为j的背包中物品的最大价值

int **value=new int

*[row];

for

(i=0;i<row;i++)

value[i]=new int

[col];

//初始化第0行

for

(j=0;j<col;j++)

value[0][j]=0;

- 8 -

8

《运筹学》课程设计报告

//初始化第0列

for

(i=0;i<row;i++)

value[i][0]=0;

//计算

for

(i=1;i<row;i++)

{

for

(j=1;j<col;j++)

{

//w[i]>j,第i个物品不装入背包

value[i][j]=value[i-1][j];

//w[i]<=j,且第i个物品装入背包后的价值>value[i-1][j],则记录当前最大价值

int

temp=value[i-1][j-w[i]]+v[i];

if

(w[i]<=j && temp>value[i][j])

value[i][j]=temp;

}

}

//逆推求装入的物品

j=m;

for

(i=row-1;i>0;i--)

{

if

(value[i][j]>value[i-1][j])

{

c[i]=1;

j-=w[i];

}

}

//记录最大价值

int

nMaxVlaue=value[row-1][col-1];

//释放该二维数组

for

(i=0;i<row;i++)

{

delete [col]value[i];

value[i]=NULL;

}

- 9 -

9

《运筹学》课程设计报告

delete[] value;

value=NULL;

return nMaxVlaue;

}

int CBeibao::GetMaxValue()

{

int nValue=GetMaxValue(m_nNumber,m_nMaxWeight,m_pWeight,m_pValue,m_pC

ount);

m_nMaxValue=nValue;

return nValue;

}

//显示结果

void CBeibao::Display(int nMaxValue)

{

printf(" %d ",nMaxValue);

for(int

i=1;i<=m_nNumber;i++)

{

if

(m_pCount[i])

printf(" %d %d ",i,m_pCount[i]);

} printf(" ");

}

void CBeibao::Display(int nMaxValue,const char *filename)

{

FILE *fp=fopen(filename,"w");

if

(fp==NULL)

{

printf("can not write file!");

return;

//exit(0);

}

fprintf(fp,"%d ",nMaxValue);

for(int

i=1;i<=m_nNumber;i++)

{

- 10 -

10

《运筹学》课程设计报告

if

(m_pCount[i])

fprintf(fp,"%d %d ",i,m_pCount[i]);

} fclose(fp);

}

//显示菜单

void show_menu()

{

printf("--------------------------------------------- ");

printf("input command to test the program ");

printf(" i or I : input filename to test ");

printf(" q or Q : quit ");

printf("--------------------------------------------- "); printf("$ input command >");

}

void main()

{

char

sinput[10];

char

sfilename[FILENAMELENGTH];

show_menu();

scanf("%s",sinput);

while

(stricmp(sinput,"q")!=0)

{

if

(stricmp(sinput,"i")==0)

{

printf(" please input a filename:");

scanf("%s",sfilename);

//获取满足最大载重量的最大价值

CBeibao beibao(sfilename);

int

nMaxValue=beibao.GetMaxValue();

if

(nMaxValue)

{

beibao.Display(nMaxValue);

- 11 -

11

《运筹学》课程设计报告

int

nlen=strlen(sfilename);

strcpy(sfilename+nlen-4,"_result.txt");

beibao.Display(nMaxValue,sfilename);

}

else

printf(" error! please check the input data! ");

5. 运行结果如下 }

//输入命令

printf("$ input command >");

scanf("%s",sinput); } }

文件中的内容如下:

1. input.txt

4 10

2 3 4 7

1 3 5 9

input_result.txt

12

2 1

4 1

2. input1.txt

5 10

2 2 6 5 4

6 3 5 4 6

input1_result.txt

15

1 1

2 1

5 1

3. input2.txt

- 12 -

12

《运筹学》课程设计报告

5 15

2 6 4 7 9

1 6 5 9 4

input2_result.txt

16

1 1

2 1

4 1

4. input3.txt

10 105

12 16 24 7 29 32 5 43 31 1 11 16 15 9 24 25 3 32 41 7

input3_result.txt

112

1 1

2 1

4 1

6 1

7 1

9 1

10 1

- 13 - 13

《运筹学》课程设计报告

五.结果分析

- 14 - 14

《运筹学》课程设计报告

成绩评定: 指导教师: 日 期:

- 15 - 15

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