完全背包问题和0

《完全背包问题和0》由会员分享，可在线阅读，更多相关《完全背包问题和0（7页珍藏版）》请在装配图网上搜索。

1、1. 实验目的(结出本次实验所涉及并要求掌握的知识点) 利用动态规划策略解决0-1 背包和完全背包问题2. 实验内容(结出实验内容具体描述)(1)0-1 Knapsack Problem 和 Unbounded Knapsack Problem 的算法进行实现(2)对O-lKnapsack Problem的算法进行空间优化，使其空间复杂度达到O(W)3. 算法描述及实验步骤(用适当的形式表达算法设计思想与算法实现步骤) l. 二维数组的 O-l 背包 空间 O(nW)int recordlOOlOO; / O-l 背包的二维表void ZO_knapsack_l(int num,int roo

2、m)/ 针对每一个物品进行筛选，看他是否是构成最终 max 的组成int i,j;for(i=O;i=num;i+)for(j=O;j=room;j+)recordij=O; / 初始化 record 表for(i=l;i=num;i+)for(j=O;jj)recordij=recordi-lj;elseif(recordi-lj-aiO+ailrecordi-lj) recordij=recordi-lj-aiO+ail; elserecordij=recordi-lj;2. 一维数组实现0-1背包 空间：O(W)int arrylOO; / 一维记录表int carry100; / 是否

3、拿走该物品记录void ZO_knapsack_2(int num,int room)int i,j;for(i=0;i=num;i+)arryi=0; / 初始化 arry 表for(i=1;i=ai0;j-)/逆序记录if(arryj-ai0+ai1arryj) arryj=arryj-ai0+ai1;3. 一维数组实现完全背包空间：0(W)void UNbounded(int num,int room)int i,j;for(i=0;i=num;i+)arryi=0; / 初始化 arry 表for(i=1;i=num;i+)for(j=ai0;jarryj) arryj=arryj-a

4、i0+ai1;4. 调试过程及运行结果（详细记录在调试过程中出现的问题及解决方法。记录实验执行 的结果）0-1 背包：SSST7ycdrd =；Draau: 00rocu: 10roca:2 flrcan:4rDc(n:6raca:80racsj：孕rcxMi： IQl:B1114Id131515入的物曲绘：5 2 1iValuei 倚一雅鬆粗实现D-aiTyt-r rM： 012L51015背包容呈，3物品个数；3输入物品重量,价値:4 20二维数组实现0-1背包:2ecord：i：0room: 00room: 10room: 2room:3roam: 40room: 0i:li:21313

5、131:3132024陵入的物品是：3 1aau維.数组实现0-1背包:mtTy 表：room:0V7=tlll 口： 仆、装入的物品是：1飞13420524完全背包|背包容it： 10物品个数：4 输入物品重量，价值士S 12 24 57 9mrry 表：room:023456了8910mine:022557910J112裝入苗物品是:T 1xVaiue: 12背包容昌：L0物品个数：5输入物品重量，价值：2 62 36 55 44 6日rry表土room:012345678910valje: 00661212IB18242430驚的物品是0 0 0 0JrtaxValue: 305. 总结

6、（对实验结果进行分析，问题回答，实验心得体会及改进意见）dpij表示将前i件物品装进限重为j的背包可以获得的最大价值，0=i=N, 0=j=W 0-1背包问题1. 不装入第 i 件物品，即 dpi-1j；2. 装入第 i 件物品（前提是能装下），即 dpi-1j-wi + vi。 完全背包1. 不装入第i种物品，即dpilj,同01背包；2. 装入第i种物品，此时和01背包不太一样，因为每种物品有无限个，所以此时不应 该转移到dpi-lj-wi而应该转移到dpijwi,即装入第i种商品后还可以再继续装入 第种商品。二者在用一维数组实现时，一个是逆序（避免覆盖），一个是顺序（需要覆盖）6. 附录

7、（程序源代码等）#include #include / 二维数组实现 0-1 背包void ZO_knapsack_1(int num,int room)/ 针对每一个物品进行筛选，看他是否是构成最终 max 的组成int i,j;for(i=0;i=num;i+)for(j=0;j=room;j+)recordij=0; / 初始化 record 表for(i=1;i=num;i+) for(j=0;jj)recordij=recordi-1j;else if(recordi-1j-ai0+ai1recordi-1j) recordij=recordi-1j-ai0+ai1;else rec

8、ordij=recordi-1j;/ 一维数组实现0-1背包int arry100; / 一维记录表int carry100; /是否拿走该物品记录void ZO_knapsack_2(int num,int room)int i,j;for(i=0;i=num;i+)arryi=0; / 初始化 arry 表for(i=1;i=ai0;j-)if(arryj-ai0+ai1arryj) arryj=arryj-ai0+ai1;/ 一维数组实现完全背包void UNbounded(int num,int room)int i,j;for(i=0;i=num;i+)arryi=0; / 初始化

9、arry 表 for(i=1;i=num;i+) for(j=ai0;jarryj) arryj=arryj-ai0+ai1;int main()int num;int room;printf(背包容量：)；scanf(%d,&room);printf(物品个数：)；scanf(%d,&num)；printf(输入物品重量，价值：n);for(int i=1；i=num；i+) scanf(%d%d,&ai0,&ai1)；/printf(n=二维数组实现 0-1 背包：=nn);/ 二维数组实现 0-1 背包/ZO_knapsack_1(num,room);/printf(nrecord 表：

10、 nt);/for(int i=0;iv=room;i+)/printf(room:%dt,i);/ for(int i=0;i=num;i+)/printf(n);/printf(i:%dt,i);/for(int j=0;j=1 &index!=0;i-)/if(recordiindex!=recordi-1index)/printf( %d,i);/index=index-ai0;/printf(nnMaxValue: %dnn,recordnumroom);/printf(二=一维数组实现 0-1 背包：=nn); / 一维数组实现 0-1 背包/ ZO_knapsack_2(num,

11、room);/ printf(narry 表：nroom:t);/for(int i=0;iv=room;i+)/printf(%dt,i);/printf(nvalue:t);/for(int i=0;i=room;i+)/printf(%dt,arryi);/printf(n装入的物品是:)；/for(int i=l;iv=num;i+)/if(arryroom=arryroom-ai0+ai1)/carryi=l;/for(int j=l;j=num;j+)/printf(%d ,carryj);/printf(nnMaxValue: %dnn,arryroom);/ 一维数组实现完全背

12、包UNbounded(num,room);printf(narry 表： nroom:t); for(int i=0;i=room;i+) printf(%dt,i);printf(nvalue:t);for(int i=0;i=room;i+) printf(%dt,arryi); printf(n装入的物品是:)； for(int i=l;i=num;i+) if(arryroom=arryroom-ai0+ail) carryi=l;for(int j=l;j=num;j+) printf(%d ,carryj);printf(nnMaxValue: %dnn,arryroom);return 0;