C语言解决背包问题

C语言解决背包问题

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkel和Hellman提出的。

首先打开VC++6.0

选择文件，新建

选择C++ source file 新建一个空白文档

首先声明头文件和常量

#include

#define NUM 10/* 定义物品总数*/

#define CONTENT 10 /*定义包的容量*/

写一个函数，用来得到多个最优解

void knapsack(int v[NUM],int w[NUM],int c,int m[NUM ][CONTENT])

{

int n=NUM-1;

int i,j;

int jMax;

if((w[n]-1)< c)

jMax = w[n]-1;

else

jMax = c;

/* 初始化m[n][j] */

for(j = 0; j <= jMax; j++)

m[n][j] = 0;

for(j = jMax +1; j <= c; j++)

m[n][j] = v[n];

/*使用非递归的算法来求解m[i][j] */

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

{

if((w[i]-1)< c)

jMax = w[i]-1;

else

jMax = c;

for(j = 0; j <= jMax; j++)

m[i][j] = m[i+1][j] ;

for(j = jMax +1; j <= c; j++)

{

if(m[i+1][j] >= (m[i+1][j-w[i]]+v[i]))

m[i][j] = m[i+1][j] ;

else

m[i][j] = m[i+1][j-w[i]]+v[i];

}

}

if(c>w)

{

if(m[c] >= (m[c-w]+v))

m[c]= m[c];

else

m[c]= m[c-w]+v;

}

else

m[c]= m[c];

}

再编写一个函数，用来寻找最优解

/*寻找最优解*/

void traceback(int flag[NUM],int w[NUM],int m[NUM][CONTENT])

{

int n = NUM -1;

int i;

int c = CONTENT;

for(i = 0; i < n; i++)

{

if(m[i][c] == m[i+1][c])

flag[i] = 0;

else

{

flag[i] = 1;

c-=w[i];

}

}

if(m[n][c] >0)

flag[n] = 1;

else

flag[n] = 0;

}

写个函数，用来输出最优解

void printResult(int flag[NUM],int w[NUM],int v[NUM],int m[NUM][CONTENT])

{

int i;

printf("the knapsack should contain:\n");

printf(" num weight value \n");

for(i = 0;i < NUM; i++)

{

if(flag[i] == 1)

printf(" %d %d %d\n",i,w[i],v[i]);

}

printf("the max value in the knapsack is: %d\n",m[CONTENT]);

}

主函数

int main()

{

int value[NUM]={5,2,3,4,3,6,5,7,8,2};

int weight[NUM]={2,1,3,2,4,3,5,6,2,2};

int c = CONTENT;

int maxvalue[NUM][CONTENT];

int flag[NUM]={0,0,0,0,0,0,0,0,0,0};

printf("****************************************\n");

printf("* this program will solve *\n");

printf("* the problem of 0-1knapsack *\n");

printf("****************************************\n");

/*计算最优值*/

knapsack(value,weight,c,maxvalue);

/*构造最优解*/

traceback(flag,weight,maxvalue);

/*打印程序的结果*/

printResult(flag,weight,value,maxvalue);

getch();

return 0;

}

运行结果