`

最优组合之背包算法

 
阅读更多

/**
 * 最优组合之背包算法
 *
 *价值:6,3,5,4,6
 *重量:2,2,6,5,4
 *载重10
 *求最大价值?
 */
class Knapsack {

 public static void main(String[] args) {
  
  int max=10;//载重
  int min=1;
  int[] jz=new int[]{6,3,5,5,6 };//对应的价值
  int[] zl=new int[]{2,2,6,5,4};//对应的重量
  int value[] =new int[max+1];//最大价值(value[max]值最大,value数组从小到大排序)
  int item[] =new int[max+1]; //放入物体
  
  for(int i=0;i<zl.length;i++){
   for(int s=zl[i];s<=max;s++){//s表示货物的重量
    int p=s-zl[i];//单位重量每增加1
    int currVal=jz[i]+value[p];//value[p]原先的重量,jz[i]新增的重量
    if(currVal>value[s]){
     value[s]=currVal;//总重量为s时的最大价值
     item[s]=i;   //增加重量zl[i]的货物到包中(item中的值相同,说明放入的是同一种货物)
    }
   }
   for(int k=0;k<=max;k++){//打印放入第k个物体的单位重量增加的最大价值
    System.out.print(value[k]+" ");
   }
   System.out.println();
  }
  
  //找出放入背包的物体
  for(int i=max;i>min;i=i-zl[item[i]]){//value[max]价值最大
   //System.out.println(i);//依此类推,除去第N个物体的总重量
   System.out.println("重量:"+zl[item[i]]+"价值:"+jz[item[i]]);
  }
 }

}

分享到:
评论

相关推荐

    java背包算法例子

    原先在网上找到某位大虾写的一个简单的背包算法,于是在其基础上改成适合我们目前项目中要求的背包算法。此算法要求传入一组对象集合(其中的对象中只包含主键和值)和某个条件值,然后能打印sum(对象.值)条件的1个...

    最优装载问题 计算机算法 c/c++语言

    最优装载问题,也被称为集装箱装载或货车装载问题,是一个经典的组合优化问题,广泛存在于物流、运输和资源分配等领域。在计算机科学中,它通常被处理为一个求解最大化的二进制背包问题,目的是在有限的容量下,尽...

    背包问题.rar_matlab算法实现背包问题_价值背包算法_背包最大价值_背包问题_遗传算法 背包

    三、价值背包算法 在本项目中,我们特别关注价值背包问题,即每个物品的价值和重量不等。在选择物品时,不仅考虑其重量,还要考虑其对整体价值的贡献。通过遗传算法,我们能够平衡重量限制与价值最大化的关系,找到...

    遗传算法解决背包问题

    本项目中,遗传算法被应用于解决经典的背包问题,这是一种典型的组合优化问题。在背包问题中,我们通常有一组物品,每件物品都有一个重量和价值,目标是在不超过背包总容量的前提下,选取物品以最大化总价值。 首先...

    贪心算法 背包问题 C语言

    贪心算法的优点是思路简单,易于实现,但并不总是能得到全局最优解,因为它的每一步选择都是局部最优的,而全局最优可能需要考虑更多的组合可能性。在背包问题中,贪心算法对于某些特定类型的问题(如完全背包、非...

    毕业论文jsp30背包算法.doc

    背包算法是计算机科学中的一种经典算法,用于解决组合优化问题。该算法的提出可以追溯到1978年,Merkel和Hellman提出了该问题。该算法的主要思想是,在给定总重量的限制下,如何选择物品,使得总价值最高。 在...

    蚁群算法_群智能算法;蚁群算法;背包问题_

    背包问题是一类典型的组合优化问题,通常涉及在给定的容量限制下,从一系列物品中选择最优组合,以使总价值最大化或总重量最小化。背包问题有多种变体,如0-1背包问题(每个物品只能取或不取)、完全背包问题(每个...

    贪心算法 背包问题 c语言

    背包问题是一类经典的组合优化问题,其基本形式为:给定一系列物品,每种物品都有一定的价值(或利润)和重量,要求从中选择若干物品放入背包中,使得总重量不超过背包容量的情况下,背包内物品的总价值最大。...

    贪心算法背包问题解决,

    背包问题是计算机科学领域内一个经典的组合优化问题,通常被用来作为算法设计与分析的案例之一。该问题可以表述为:给定一系列物品,每件物品有一个重量和一个价值;另有一个背包,其容量有限。目标是在不超过背包...

    背包算法经典

    ### 背包算法经典:深入解析背包九讲 #### 第一讲:01背包问题 **知识点概览**:01背包问题是最基础的背包问题类型,涉及到的每种物品仅有一件,且每件物品只能选择放入背包或不放入背包。此问题通过动态规划方法...

    PSO04_粒子群算法_背包算法_

    总结来说,本案例通过粒子群算法解决了背包问题,利用群体智能寻找最优的物品选择方案,体现了PSO在处理复杂优化问题上的潜力。通过深入理解并实践这种算法,我们可以解决许多实际工程和科学领域的优化挑战。

    背包问题PSO算法代码

    背包问题通常是一个组合优化问题,其中我们需要决定如何在给定容量限制的背包中选择物品,以最大化价值或重量。PSO算法在此场景下可以作为一种搜索策略,帮助我们遍历可能的解决方案空间,找到最优解。 【标签】...

    背包问题贪婪算法

    贪心算法并不总是能找到全局最优解,但在某些特定情况下,如背包问题,它能提供一个接近最优的解决方案。贪心算法的步骤通常是:对问题进行分解,然后在每一步选择局部最优解,希望这些局部最优解组合起来能得到全局...

    背包算法+近似算法+近似方案

    ### 背包算法+近似算法+近似方案 #### 一、引言与背景 背包问题(Knapsack Problem)是计算机科学与运筹学中的一个经典问题,广泛应用于资源分配、优化决策等领域。它主要研究的是如何在有限的资源约束下,通过...

    0-1背包问题(贪心算法)C语言源程序

    0-1背包问题是一种经典的组合优化问题,在实际应用中有着广泛的应用场景,比如物流分配、资源调度等领域。该问题的核心是:给定一系列物品(每个物品有其价值和重量),以及一个背包的最大承重能力,要求在不超过...

    四种算法写0-1背包

    贪心算法通常不是解决0-1背包问题的最优方法,因为它无法保证全局最优解。贪心策略可能会选取局部最优的物品,但忽视了整体的最优解。例如,贪心算法可能会优先选择价值/重量比高的物品,但这可能导致背包空间的浪费...

    贪心算法解决背包问题

    在背包问题中,贪心算法通常用于解决“最佳装载”背包问题,即在不超过背包最大重量限制的情况下,选择价值最大的物品组合。 **最佳装载背包问题** 在这个问题中,我们可以将物品按照单位重量的价值(价值除以重量...

    遗传量子算法背包问题

    6. **解码**:最后,将最优的个体解码为实际的物品选择方案,即背包问题的最优解。 MATLAB作为一个强大的数值计算环境,提供了丰富的工具箱支持优化算法的实现,包括遗传算法和量子计算的相关库。开发者可以根据...

    0/1背包算法与决策树ID3算法实现

    0/1背包算法与决策树ID3算法实现 本文主要讨论了 0/1 背包动态规划算法与决策树 ID3 算法的实现 DETAILS 。 0/1 背包问题 0/1 背包问题是一种组合优化的 NP 完全问题。问题可以描述为:给定一组物品,每种物品都...

Global site tag (gtag.js) - Google Analytics