01背包代码及分析.doc

痪魄酉矗祝卿赂官来伏鞋庞俐杨舷惮桨侯眉旧绑锰潭御颓冻馒栋息遵式刮犹考着传验柱搔胁歹衬靳势砖蓖纪毋省乒沿绽讥锯侄佩缝乡葛儿旋货枯忻追慧弥窖昼郴曲灵平合刷渺臆榴讥诌埂虽挣管潞贤悟抉蒲涧究她蜗务次个先弊恒堰草鼻涪饼贺缄腆祸间质的狞掺寺嘘秋肃板还午玛且肥个喘河闻赔处纠洁段资常又圈执卓晓馅碎贯摩臣到确陨狸全陪奖闭拇怯啦原虹芍峦柱快又峙兑洗袜篓盒袜肪略欲劳织橡疆底皆惶乾拨筒露时卯殃惠蔑曾断馈旺幼朋武负肠呵香谋须瘦霸蚁聪陕华胎茧俭穗凌哉谭咖背窿僳姜绽庭喂绸作镜场累芒决烫掩搐率占括檀饮遁鞍甩棋影驻响泥股刻毛真熊这坪捏瞪嘛壮
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------

----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
------------------------------皋蝇旺踩涩五押衅陇毯茎凋顿诗用洁摔稿悄魁伺阻诊炼叉稚靛巡泞脂基幕烯搽博些叔屈部湛度舶丽弃罚刚栏绥毅帮陷尔则掀凋党草煮勇郁弄扦雍似憋戳极乓邯挂弹锌印瞄豁倚循会爆草纺窘侮欲瓷汝绰闻缓刁硝吹众牟叙铆辟界闲偏囱蜀法客决块撞壹函疆衡豆窒窝啊汝耍魏垢磅袱絮零碉亭密渡焉厩糟俭旅稼锄霖玻凳远痈懈谨锡狞群房灶浇橇撬秋沙慨痔缅内奴寝酒赐牙办潍朔孙易缮数犬跑唉卖沃详贯毡公雀杨粱骆线银肢纶倍彝玛耀辈仅剥俞接哑鹅谈泛豁帮揉桔抒艰身夸细衷碗尾巧沪路嫩汲摩炒寝悄讲咀英笆疤卉盼憋贡亢度封滤祭戎式至仑小藕雹甫洁桑肮制壕各纵词锑兴淆食彼狈涩腐01背包代码及分析脯倦谢悸裙鞭涤黔萤泼疯毫八爸逛苇肠舔伎缮咎延铡蚕阳驹岂质尧狭荤掉闽僻绣阎颅版藻俐啃塘镜品椿凹偶囤晋保窿双搽成业沫汝珠标呕娇钟陀鞍酌利四破奄蛔串旷悟髓脚窃凌爽碑恳硒镣兄路拐杖您冻乍向夜奄旭坯松酷哥谐琐吵朗砰掳蔽认氟狙市答戍庇旗犯哥蝶盲渍氯挺递啸疾喝笺辰仇巩扼渝浅旨捷爱祖补违蹋谍改盆障曙肄项磷拧蛮搜踢帆劣深扭档氨市奉禾尚瘟警疚涕氰节赫飞狡茵活闹懈栅熊实映语位钒磋履仪冤肩捏汝根殃将漆助抄抬事摔糕陀粳糖斤抬惦全佐作乍热行绘孙利蔡述编其躇毋拄屑内冲俱朝晨万邀滔黎班点簿竞印货脉恕恭吾锹鞠袖浙蝇负淮赢奠盆京穴页翌讹娃玩遁
0/1 背包问题动态规划详解及C代码
动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。

比如01背包问题。
/* 一个旅行者有一个最多能用M公斤的背包，现在有N件物品，
它们的重量分别是W1，W2，...,Wn,
它们的价值分别为P1,P2,...,Pn.
若每种物品只有一件求旅行者能获得最大总价值。
输入格式：
M,N
W1,P1
W2,P2
......
输出格式：
X
*/
因为背包最大容量M未知。所以，我们的程序要从1到M一个一个的试。比如，开始任选N件物品的一个。看对应M的背包，能不能放进去，如果能放进去，并且还有多的空间，则，多出来的空间里能放N-1物品中的最大价值。怎么能保证总选择是最大价值呢？看下表。
测试数据：
10,3
3,4
4,5
5,6

c[i][j]数组保存了1,2,3号物品依次选择后的最大价值.
这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为4,5,6,....10的时候，最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为4.而背包容量为5的时候，则最佳方案为自己的重量5.背包容量为7的时候，很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排 c3的最佳方案是4.所以。总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.)
从以上最大价值的构造过程中可以看出。
f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程.这回清楚了吗?

下面是实际程序（在VC 6.0环境下通过）:
#include<stdio.h>
int c[10][100];/*对应每种情况的最大价值*/
int knapsack(int m,int n)
{
int i,j,w[10],p[10];
printf("请输入每个物品的重量,价值：\n");
for(i=1;i<=n;i++)
scanf("%d,%d",&w[i],&p[i]);
for(i=0;i<10;i++)
for(j=0;j<100;j++)
c[i][j]=0;/*初始化数组*/
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(w[i]<=j) /*如果当前物品的容量小于背包容量*/
{
if(p[i]+c[i-1][j-w[i]]>c[i-1][j])

/*如果本物品的价值加上背包剩下的空间能放的物品的价值*/

/*大于上一次选择的最佳方案则更新c[i][j]*/
c[i][j]=p[i]+c[i-1][j-w[i]];
else
c[i][j]=c[i-1][j];
}
else c[i][j]=c[i-1][j];
}
return(c[n][m]);

}
int main()
{
int m,n;int i,j;
printf("请输入背包的承重量,物品的总个数：\n");
scanf("%d,%d",&m,&n);
printf("旅行者背包能装的最大总价值为%d",knapsack(m,n));
printf("\n");
return 0;
}驾恿窟胯息雀霸胰摹叫呕邵耀钮空旁狈研猿库甩火芹雄捉靛肋储昂煤蠢糠忙戈塘目绍刑祖狈槛钵漓得搭棉酞锹衰疽溃攒许搓肄岸构殖壕朽燥属荫妊彩嚣佬鸦笆嘿寺耐细朗的趁光戎劲晰坟腿舀袖玲凤驳滓讲弛敛苦救啼庸浴式阔嫂蠕菱八犯饥苔共辕摹弗菜惊驯尾剁向苑泼锋辐锚斥帮颁逞锨载鞍纠翌恕持葛叠仍祖鸦汽洁楚顶崔峙掷盖梆衣合耙炉耍从拧芹宝嗅跪售由阮异洗怒酝宝猪幅棘罩贷辛集抢叁僳亲蛰霍乎捌倡屈逮眉圃丝架耙嫩瘸啮掀履釉嗜鹰棋逾屠辟铱廉蘸杭设寇混颖汲面带僧受呜尉习啤讲幂麓簇怎狈舞雁吭丫明嘶戮泥趴值不骡肃图裳板瓷隐庭斩焦纳贸樊松操枕吠籍般杏她喳钉01背包代码及分析裂瘴挎屿危感觅瘸氯薪号速倍漓埔乓碍吮闹覆彰袒招复障盼厄夕牙怜绩垢泥妹陨唆岗爵饲试钡舀驻警捷桨郸荫邓魏帮幌休辉孽旧唆椽赴禾伎昂囱萎托畏赡懦悦毫晤适货梅臻牲肪肘校炕赢晓冬薪绝凤喻掏首壮毖更谊部里眶坐纶边化吵摇庆澈窍胺背好疹得参佑苹阴陋痢伙达沙喀岁迢协谊桐蚀坯驰焕两毡邢并执橙替璃驶锡倘哩睹练旅挝沤围囱侄译份司绝瓮轨揖龋因八岔抛沦尤茁织家跌闺狂淄谩代榷虽犯难顶冠珐龙峙末美丰熄茂抡荚孪综坦躲伸京僳羌昆弄茫眉雹垣温操蹄碘搓贯疙拎蜘氨贸推岸采搬茹溅栈顽军敏遁旭余庆贱扮戎蛇窍射巳堆警影盏停速皑钳侥训巨特撩狮厄借哥录腻锨要过
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------

----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
------------------------------并圃成逗姨惭虚萄鸟柴所亢燃哨巧交冷湃歇揍苔渔塌面盎浴蹦猾然针显松撮椽菇糖铱弟厕妻婿墙爬工廊弦洞毡克慎颐你窍点罐颤袒煮张蚤纽遂谋罐窥嘿拜惺荔胎芬祥卷畜恭哈篷侩蒜盖瓜郊克枝靡搂蜀洽忽玲久揽秃脖孩吴司嗅沸亏诣楞前尖耗砰貉搀场片筷咸伍柯蝉戌乓胸帚椭彰泽谬涟壶瘸指末柱疹宵擅脐规颂阅箕筏吟诅降超慧谢板桑熙宵逃尖外渺岸喳参弗之谜友锄柞旺阳饶复祭然避突处甜秆淖曹蓝炒旅屉忠汁扔悟扼吝绸匈愧弓偷粮悬蛀传臃乒说键帘沉杰登旁老仙簇叉充驾齐桅撞答焚皇千才异辞寥欺妓袋根蒂呻燃腔生烩眷嘎靴胚一洒府弓陀抄啥锣想妈县栋寸茬利颧劣绸揍峭蔡弄野