问题说明:
假设一个背包的负重最大可达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)是一个经典的组合优化问题,通常分为两种类型:0/1背包问题和分数背包问题。 1. **0/1背包问题**: - 给定一组物品,每个物品都有自己的重量和价值,要求在给定的背包容量下,选择...
背包问题(Knapsack problem)是一种组合优化的NP完全问题
01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下: 给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择...
背包问题: 01背包问题 02: 完全背包问题 03: 多重背包问题 04: 混合三种背包问题 05: 二维费用的背包问题 06: 分组的背包问题 07: 有依赖的背包问题 08: 泛化物品 09: 背包问题问法的变化 11: 背包问题的搜索解法
背包问题(Knapsack problem)是组合优化领域的一类经典问题: 给定一个物品集合,每个物品具有一定重量以及一定的价值. 对于一个承载重量有限的背包,如何决定放入的物品,使得在背包承载的范围内获取所装物品的最大...
背包问题,算法的背包问题 背包问题,算法的背包问题 背包问题,算法的背包问题
【背包问题】基于遗传算法求解多背包问题matlab源码
算法效果较为良好,实现背包问题价值最大,采用遗传算法实现的比较不错的结果
用禁忌搜索算法求解背包问题。假设背包容量一定,已知每种物品的体积和价值,求出使价值最大的最优解。
《背包问题九讲》,dd_engi大神...目录:1、01背包问题;2、完全背包问题;3、多重背包问题;4、混合三种背包问题;5、二维费用背包问题;6、分组的背包问题;7、有依赖的背包问题;8、泛化物品;9、背包问题的变化;
算法课程设计 背包问题 0/1背包问题 实现算法课程设计 背包问题 0/1背包问题 实现 算法课程设计 背包问题 0/1背包问题 实现算法课程设计 背包问题 0/1背包问题 实现 算法课程设计 背包问题 0/1背包问题 实现 算法...
【背包问题】基于PSO算法求解01背包问题
贪心算法 背包问题 c语言 绝对无误 运行成功
使用遗传算法解决0-1背包问题,调试成功,非常适合初学者了解遗传算法和0-1背包问题
简单的遗传算法用于解决背包问题codeblocks编写,运行成功
实验目的:0/1背包问题的回溯算法设计 实验原理:回溯算法设计。 实验要求:基本掌握回溯算法设计的原理方法。熟练掌握VC++中编程实现算法的常用技术和方法。 算法思想: 0-1背包问题:给定n种物品和一背包.物品i的...
C++ 0-1背包问题源代码
第一讲 01背包问题 这是最基本的背包问题,每个物品最多只能放一次。 第二讲 完全背包问题 第二个基本的背包问题模型,每种物品可以放无限多次。 第三讲 多重背包问题 每种物品有一个固定的次数上限。 第四讲 ...
此文章讲述了经典的背包问题,以及各种背包问题的变种,是学习算法比较好的东西,也有助于学习各种思想,进一步提高我们解决问题的能力
贪婪法解决01背包问题贪婪法解决01背包问题贪婪法解决01背包问题贪婪法解决01背包问题