01背包问题

实 验 报 告

实验名称：01 knapsack problem 任课教师：

专 业： 学号： 姓 名：

完成日期：2014.1.8 成绩：________________

一、实验目的： 1、掌握0—1背包问题的回溯算法； 2、进一步掌握回溯算法； 二、实验内容： 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 三、程序设计说明：(算法设计思路) 找一棵树来表示各个商品装入的情况，第一层有两种结果，分别代表商品1装入与未装入，以此类推，先初始化所有为-1。先取第一件判断能否装入，若能，则装入并更改-1为1，继续第二层，直到k=n，并得到最优值l。然后回溯，取另一分支，比较最优值，如此循环直到回到第0层。 四、程序代码（经调试正确的源程序） using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace _01_knapsack_problem { class Program { static void Main(string[] args) { int[] w = { 0, 3, 1, 5, 8, 4, 6 }; int[] p = { 0, 15, 10, 20, 32, 12, 5 }; int c = 15; huisu(w, p, c); } static void huisu(int[] w, int[] p, int c) { int cw = 0; int cp = 0; int fp = 0; int[] y = new int[7] { -1, -1, -1, -1, -1, -1, -1 }; int[] x = new int[7] { 0, 0, 0, 0, 0, 0, 0 }; int k = 1; while (k > 0) { if (y[k] != 0) { if (y[k] == -1) { if (cw + w[k] <= c) { y[k] = 1; cw += w[k]; cp += p[k]; } else { y[k] = 0; } } else if (y[k] == 1) { cw -= w[k]; cp -= p[k]; y[k] = 0; } if (k == w.Length - 1) { if (cp > fp) { fp = cp; for (int i = 1; i < w.Length; i++) { x[i] = y[i]; } } } else k++; } else { y[k] = -1; k--; } } Console.WriteLine(\"注：1代表装入，0代表不装入\"); Console.Write(\"最优价值\"); Console.WriteLine(fp); Console.WriteLine(\"最优方案商品为：\"); for (int i = 1; i < w.Length; i++) { Console.Write(x[i]); } Console.ReadLine(); } } } 五．程序运行结果（测试数据和运行结果）六、算法复杂性分析（对所编写程序的时间复杂性和空间复杂性的分析） T(n)=n！ 七、实验中遇到的问题及解决方法 八、实验总结 注：实验报告填写时，注意输入信息的字体格式（宋体、五号），如果用复制应采用选择性粘贴的 “无格式文本”方法完成；“程序运行结果”请以屏幕拷贝的方式将运行结果的截图复制在报告中。