算法分析与设计 |
您所在的位置：网站首页 › 记录十种物品的重量英文 › 算法分析与设计 |
|
蛮力法0/1背包
蛮力法
蛮力法是一种简单直接解决问题的方法，常常直接基于问题的描述，所以蛮力法也是最容易应用的方法。 蛮力法所依赖 的基本技术是遍历，即采用一定的策略依次处理待求解问题的所有元素，从而找出问题的解。由于其需要依次穷举待处理的元素，因此蛮力法是一种典型的指数级时间算法。 问题给定n个重量为{w1,w2,···,wn}、价值为{v1,v2,···,vn}的物品和一个容量为C的背包，0/1背包是一个求解这些物品中的一个最有价值的子集，并且能够装入到背包中。 应用实例有n项可投资的项目，每个项目需要投入资金si，可获利润为vi，现有可用资金M，应选择那些项目来投资才能获得最大利润。 想法用蛮力法解决0/1背包问题，需要考虑给定n个物品集合的所有子集，找出所有重量不超过背包容量的子集，计算每个可能子集的总价值，然后找到价值最大的子集。例如，给定4个物品的重量为{7,3,4,5}，价值为{42,12,40,25}，和一个容量为10的背包，下表为求解的过程。 序号子集总重量总价值1∅002{1}7423{2}3124{3}4405{4}5256{1,2}10547{1,3}11不可行8{1,4}12不可行9{2,3}75210{2,4}83711{3,4}96512{1,2,3}14不可行13{1,2,4}15不可行14{1,3,4}16不可行15{2,3,4}12不可行16{1,2,3,4}19不可行 伪代码输入：重量{w1,w2,···,wn}，价值{v1,v2,···,vn}，容量C 输出：装入背包的物品编号 初始化最大价值maxValue=0；结果子集S=∅；对集合{1,2,···,n}的每一个子集T，执行如下操作： 2.1 初始化背包的价值value=0；背包的重量weight=0； 2.2 对子集T的每一个元素j 2.2.1 如果weight+wj＜C，则weight=weight+wj；value=value+vj； 2.2.2 否则，转入步骤2考察下一个子集； 2.3 如果maxValue＜value，则maxValue=value；S=T；输出S中的各元素； 源代码 #include #include #include //用于计算程序运算时间 #include using namespace std; #define N 100 struct goods{ int sign;//物品序号 int wight;//物品重量 int value;//物品价值 }; int n, maxValue, cv, cw, C;//物品数量，价值最大，当前价值，当前重量，背包容量 int X[N],cx[N];//最终存储状态，当前存储状态 struct goods goods[N]; int Force(int i) { if(i > n-1) { if(maxValue |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |