问题说明:
假设一个背包的负重最大可达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实现; 背包问题:...
《基于MATLAB的遗传算法在背包问题中的应用》 背包问题是一种典型的组合优化问题,广泛存在于资源分配、项目选择等领域。在本项目中,我们利用MATLAB强大的计算能力,结合遗传算法,对背包问题进行了有效的求解,以...
背包问题(Knapsack Problem)是计算机科学和运筹学领域中的一个经典问题,属于组合优化的一种。该问题的主要目标是在一定的约束条件下(如背包的容量),通过选择一系列物品来最大化某个指标(通常是价值)。根据...
标题中的“背包问题数据集”指的是在运筹学和计算机科学领域中常见的一种优化问题,称为背包问题(Knapsack Problem)。这个问题的基本形式是:给定一组物品,每种物品都有一个重量和一个价值,目标是在不超过给定...
背包问题: 01背包问题 02: 完全背包问题 03: 多重背包问题 04: 混合三种背包问题 05: 二维费用的背包问题 06: 分组的背包问题 07: 有依赖的背包问题 08: 泛化物品 09: 背包问题问法的变化 11: 背包问题的搜索解法
背包问题(Knapsack problem)是一种组合优化的NP完全问题
0-1背包问题是一种经典的组合优化问题,在计算机科学和运筹学中有着广泛的应用。它描述的是这样的场景:你有一组物品,每件物品都有一个重量和价值,你需要选择一部分物品放入容量有限的背包中,使得背包中的物品总...
算法设计与分析实验之背包问题 背包问题是计算机科学中的一种经典问题,属于组合优化问题。该问题的目标是从给定的物品集中选择一部分物品,以使得背包的价值最大化,而不超过背包的容量限制。 在给定的源代码中,...
《背包问题九讲》,dd_engi大神...目录:1、01背包问题;2、完全背包问题;3、多重背包问题;4、混合三种背包问题;5、二维费用背包问题;6、分组的背包问题;7、有依赖的背包问题;8、泛化物品;9、背包问题的变化;
### 贪心算法在背包问题中的应用及C语言实现 #### 一、贪心算法简介 贪心算法是一种在每个步骤中都选择局部最优解的策略,希望通过一系列的局部最优选择来达到全局最优解的目的。它适用于某些特定的问题类型,在...
背包问题有许多变种,例如完全背包问题、多重背包问题、混合三种背包问题、二维费用的背包问题、分组的背包问题、有依赖的背包问题等。这些变种问题通常在物品的限制条件、背包的限制条件或者物品的价值函数等方面...
在IT领域,优化问题是一个广泛的研究方向,其中背包问题是经典的组合优化问题之一。"禁忌搜索背包问题"是指利用禁忌搜索算法来寻找背包问题的最优解。在这个问题中,我们有一个固定容量的背包,以及一系列物品,每件...
**背包问题**是一种经典的组合优化问题,广泛应用于资源分配、项目选择、投资组合优化等领域。在该问题中,我们有一组物品,每种物品都有一个重量和一个价值,我们需要将这些物品放入一个容量有限的背包中,以使背包...
背包问题的贪心算法 背包问题是计算机科学中的一种经典问题,它是指给定一组物品和一个背包,对每种物品都有其重量和价值,背包也有其容量限制。目标是选择装入背包的物品,使得装入背包中物品的总价值最大。 贪心...
【背包问题】是一种经典的组合优化问题,广泛应用于资源分配、任务调度等领域。在这个问题中,我们有一个容量有限的背包和一系列物品,每件物品都有一个重量和价值。目标是在不超过背包容量的前提下,选择物品以最大...
### 背包问题详解及变种解析 #### 一、引言 背包问题作为计算机科学与算法领域中的经典问题之一,在实际应用中具有广泛的意义。它不仅涉及到动态规划的核心思想,而且通过不同的变种形式,能够帮助我们深入理解...
【标题】"背包问题PSO算法代码"涉及的是在计算机科学和优化技术中的经典问题——背包问题,结合了粒子群优化(PSO)算法来寻找解决方案。粒子群优化是一种受到鸟类群体行为启发的全局优化算法,它通过模拟群体中个体...
这里我们关注的是一个经典的数据结构问题——背包问题。背包问题是一类优化问题,常见于运筹学、计算机科学和算法设计中。在本案例中,我们将讨论如何用C语言和栈来解决这类问题。 首先,让我们了解背包问题的基本...
0-1背包问题是一种经典的计算机科学中的组合优化问题,它源于实际生活中的资源分配问题,例如在有限的容量下选择最有价值的物品进行携带。在这个问题中,我们有一组物品,每种物品都有一个重量和一个价值,目标是...
在解决背包问题时,贪心算法的应用尤为常见,尤其是对于部分背包问题。 0-1背包问题是最基础的形式,其中每个物品要么完全放入背包,要么完全不放。但在部分背包问题中,我们可以选择物品的一部分进行装入,这样...