| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1779 人关注过本帖, 2 人收藏
标题:0-1背包问题
只看楼主 加入收藏
无悔选择
Rank: 1
等 级:新手上路
威 望:1
帖 子:45
专家分:0
注 册:2005-12-25
收藏(2)
 问题点数:0 回复次数:2 
0-1背包问题

0 / 1背包问题中,需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品,每件物品i 的重量为wi ,价值为pi 。对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高。

程序如下:

搜索更多相关主题的帖子: 背包 
2006-04-08 15:13
无悔选择
Rank: 1
等 级:新手上路
威 望:1
帖 子:45
专家分:0
注 册:2005-12-25
收藏
得分:0 

#include <stdio.h>

void readdata();

void search(int);

void checkmax();

void printresult();

int c=35, n=10; //c 背包容量;n:物品数

int w[10], v[10]; //w[i]v[i]:第i件物品的重量和价值

int a[10], max; //a数组存放当前解各物品选取情况;max:记录最大价值

//a[i]=0表示不选第i件物品,a[i]=1表示选第i件物品

int main()

{

readdata(); //读入数据

search(0); //递归搜索

printresult();

}

void search(int m)

{

if(m>=n)

checkmax(); //检查当前解是否是可行解,若是则把它的价值与max比较

else

{

a[m]=0; //不选第m件物品

search(m+1); //递归搜索下一件物品

a[m]=1; //不选第m件物品

search(m+1); //递归搜索下一件物品

}

}

void checkmax()

{

int i, weight=0, value=0;

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

{

if(a[i]==1) //如果选取了该物品

{

weight = weight + w[i]; //累加重量

value = value + v[i]; //累加价值

}

}

if(weight<=c) //若为可行解

if(value>max) //且价值大于max

max=value; //替换max

}

void readdata()

{

int i;

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

scanf("%d%d",&w[i],&v[i]); //读入第i件物品重量和价值

}

void printresult()

{

printf("%d",max);

}


2006-04-08 15:15
快速回复:0-1背包问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.056422 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved