`
橡树心
  • 浏览: 47991 次
  • 性别: Icon_minigender_1
  • 来自: 济南
社区版块
存档分类
最新评论

背包问题(Kanpsack Problem)

 
阅读更多
问题说明:

假设一个背包的负重最大可达8公斤,而希望在背包内放置负重范围你价值最高的物品。
class Fruit {
    private String name;
    private int size;
    private int price;
    
    public Fruit(String name, int size, int price) {
        this.name = name;
        this.size = size;
        this.price = price;
    }
    
    public String getName() {
        return name;
    }

    public int getPrice() {
        return price;
    }

    public int getSize() {
        return size;
    }
}

public class Knapsack {
    public static void main(String[] args) {
        final int MAX = 8;
        final int MIN = 1;
        int[] item = new int[MAX+1]; 
        int[] value = new int[MAX+1];  

        Fruit fruits[] = {
                new Fruit("李子", 4, 4500), 
                new Fruit("苹果", 5, 5700), 
                new Fruit("桔子", 2, 2250), 
                new Fruit("草莓", 1, 1100), 
                new Fruit("甜瓜", 6, 6700)}; 

        for(int i = 0; i < fruits.length; i++) { 
            for(int s = fruits[i].getSize(); s <= MAX; s++) { 
                int p = s - fruits[i].getSize(); 
                int newvalue = value[p] + 
                                   fruits[i].getPrice(); 
                if(newvalue > value[s]) {// 找到阶段最佳解 
                    value[s] = newvalue; 
                    item[s] = i; 
                } 
            } 
        } 

        System.out.println("物品\t价格"); 
        for(int i = MAX; 
            i >= MIN; 
            i = i - fruits[item[i]].getSize()) { 
            System.out.println(fruits[item[i]].getName()+ 
                    "\t" + fruits[item[i]].getPrice()); 
        } 

        System.out.println("合计\t" + value[MAX]);  
    }
}
分享到:
评论

相关推荐

    经典背包问题(Knapsack Problem)的Java和Python实现

    背包问题:经典背包问题(Knapsack Problem)的Java和Python实现; 背包问题:经典背包问题(Knapsack Problem)的Java和Python实现; 背包问题:经典背包问题(Knapsack Problem)的Java和Python实现; 背包问题:...

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

    《基于MATLAB的遗传算法在背包问题中的应用》 背包问题是一种典型的组合优化问题,广泛存在于资源分配、项目选择等领域。在本项目中,我们利用MATLAB强大的计算能力,结合遗传算法,对背包问题进行了有效的求解,以...

    背包问题.docx 背包问题(Knapsack Problem)是一个经典的组合优化问题,通常分为两种类型:0/1背包问题和分

    背包问题(Knapsack Problem)是计算机科学和运筹学领域中的一个经典问题,属于组合优化的一种。该问题的主要目标是在一定的约束条件下(如背包的容量),通过选择一系列物品来最大化某个指标(通常是价值)。根据...

    背包问题数据集

    标题中的“背包问题数据集”指的是在运筹学和计算机科学领域中常见的一种优化问题,称为背包问题(Knapsack Problem)。这个问题的基本形式是:给定一组物品,每种物品都有一个重量和一个价值,目标是在不超过给定...

    背包问题 数学建模 背包问题 数学建模

    背包问题: 01背包问题 02: 完全背包问题 03: 多重背包问题 04: 混合三种背包问题 05: 二维费用的背包问题 06: 分组的背包问题 07: 有依赖的背包问题 08: 泛化物品 09: 背包问题问法的变化 11: 背包问题的搜索解法

    背包问题.zip_Knapsack Problem _NP问题_完全背包_背包 问题_背包问题

    背包问题(Knapsack problem)是一种组合优化的NP完全问题

    matlab程序(解决0-1背包问题).zip_背包_背包算法 matlab_背包问题_遗传算法 背包_遗传算法背包

    0-1背包问题是一种经典的组合优化问题,在计算机科学和运筹学中有着广泛的应用。它描述的是这样的场景:你有一组物品,每件物品都有一个重量和价值,你需要选择一部分物品放入容量有限的背包中,使得背包中的物品总...

    算法设计与分析实验之背包问题

    算法设计与分析实验之背包问题 背包问题是计算机科学中的一种经典问题,属于组合优化问题。该问题的目标是从给定的物品集中选择一部分物品,以使得背包的价值最大化,而不超过背包的容量限制。 在给定的源代码中,...

    背包问题九讲2.0最新版

    《背包问题九讲》,dd_engi大神...目录:1、01背包问题;2、完全背包问题;3、多重背包问题;4、混合三种背包问题;5、二维费用背包问题;6、分组的背包问题;7、有依赖的背包问题;8、泛化物品;9、背包问题的变化;

    贪心算法 背包问题 c语言

    ### 贪心算法在背包问题中的应用及C语言实现 #### 一、贪心算法简介 贪心算法是一种在每个步骤中都选择局部最优解的策略,希望通过一系列的局部最优选择来达到全局最优解的目的。它适用于某些特定的问题类型,在...

    背包问题九讲 2.0 RC1

    背包问题有许多变种,例如完全背包问题、多重背包问题、混合三种背包问题、二维费用的背包问题、分组的背包问题、有依赖的背包问题等。这些变种问题通常在物品的限制条件、背包的限制条件或者物品的价值函数等方面...

    禁忌搜索背包问题,禁忌搜索算法解决背包问题,matlab

    在IT领域,优化问题是一个广泛的研究方向,其中背包问题是经典的组合优化问题之一。"禁忌搜索背包问题"是指利用禁忌搜索算法来寻找背包问题的最优解。在这个问题中,我们有一个固定容量的背包,以及一系列物品,每件...

    背包问题 Matlab 求解

    **背包问题**是一种经典的组合优化问题,广泛应用于资源分配、项目选择、投资组合优化等领域。在该问题中,我们有一组物品,每种物品都有一个重量和一个价值,我们需要将这些物品放入一个容量有限的背包中,以使背包...

    背包问题的贪心算法,背包问题的贪心解法

    背包问题的贪心算法 背包问题是计算机科学中的一种经典问题,它是指给定一组物品和一个背包,对每种物品都有其重量和价值,背包也有其容量限制。目标是选择装入背包的物品,使得装入背包中物品的总价值最大。 贪心...

    背包问题的贪心法C语言实现

    【背包问题】是一种经典的组合优化问题,广泛应用于资源分配、任务调度等领域。在这个问题中,我们有一个容量有限的背包和一系列物品,每件物品都有一个重量和价值。目标是在不超过背包容量的前提下,选择物品以最大...

    背包问题,详细讲解几种背包问题

    ### 背包问题详解及变种解析 #### 一、引言 背包问题作为计算机科学与算法领域中的经典问题之一,在实际应用中具有广泛的意义。它不仅涉及到动态规划的核心思想,而且通过不同的变种形式,能够帮助我们深入理解...

    背包问题PSO算法代码

    【标题】"背包问题PSO算法代码"涉及的是在计算机科学和优化技术中的经典问题——背包问题,结合了粒子群优化(PSO)算法来寻找解决方案。粒子群优化是一种受到鸟类群体行为启发的全局优化算法,它通过模拟群体中个体...

    经典数据结构问题 背包问题所有解

    这里我们关注的是一个经典的数据结构问题——背包问题。背包问题是一类优化问题,常见于运筹学、计算机科学和算法设计中。在本案例中,我们将讨论如何用C语言和栈来解决这类问题。 首先,让我们了解背包问题的基本...

    0-1背包问题

    0-1背包问题是一种经典的计算机科学中的组合优化问题,它源于实际生活中的资源分配问题,例如在有限的容量下选择最有价值的物品进行携带。在这个问题中,我们有一组物品,每种物品都有一个重量和一个价值,目标是...

    贪心算法 背包问题 C语言

    在解决背包问题时,贪心算法的应用尤为常见,尤其是对于部分背包问题。 0-1背包问题是最基础的形式,其中每个物品要么完全放入背包,要么完全不放。但在部分背包问题中,我们可以选择物品的一部分进行装入,这样...

Global site tag (gtag.js) - Google Analytics