与0-1 背包问题类似,所不同的是在选择物品i 装入背包时,可以选择物品i 的一部分,而不一定要全部装入背包.
算法分析:
首先计算每种物品的单位重量的价值, 然后依贪心策略,将尽可能多的单位重量价值最高的物品装入背包.
实现:
/*
* description: 背包问题
* 问题描述:与0-1背包问题类似,所不同的是在选择物品i装入背包时,可以选择
* 物品i的一部分,而不一定要全部装入背包.
* 算法分析:贪心算法
* 首先计算每种物品的单位重量的价值,然后依贪心策略,将尽可能多的单位重量价值最高的物品装入背包.
*
* date: 2010/12/5
* auther:cm
*/
import java.util.Arrays;
import java.util.Collections;
public class Pack
{
//物品数组
private Goods[] g;
//最大价值
private double maxValue;
//背包容量
private double c;
public Pack(double[] w, double[] v, double c)
{
int n = w.length;
g = new Goods[n];
//初始化
for (int i = 0; i < n; i++)
{
g[i] = new Goods(w[i], v[i]);
}
this.c = c;
}
public double pack()
{
Arrays.sort(g,Collections.reverseOrder());//按性价比排序 由大到小
double value = 0.0;
double this_c = c;
for (int i = 0; i < g.length; i++)
{
if (this_c >= g[i].getWeight())
{
value += g[i].getValue();
this_c -= g[i].getWeight();
}
else
{
value += this_c * g[i].getAverage();
break;
}
}
maxValue = value;
return value;
}
public void print()
{
for (int i = 0; i < g.length; i++)
{
System.out.print(g[i].getAverage() + " ");
}
}
public static void main(String[] args)
{
double[] w = {10,20,30};
double[] v = {60, 100, 120};
double c = 50;
Pack p = new Pack(w, v, c);
System.out.println(p.pack());
//p.print();
}
}
注:使用贪心策略无法解决0-1背包问题
分享到:
相关推荐
01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下: 给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择...
实验目的:0/1背包问题的回溯算法设计 实验原理:回溯算法设计。 实验要求:基本掌握回溯算法设计的原理方法。熟练掌握VC++中编程实现算法的常用技术和方法。 算法思想: 0-1背包问题:给定n种物品和一背包.物品i的...
《背包问题九讲》,dd_engi大神...目录:1、01背包问题;2、完全背包问题;3、多重背包问题;4、混合三种背包问题;5、二维费用背包问题;6、分组的背包问题;7、有依赖的背包问题;8、泛化物品;9、背包问题的变化;
背包问题的一种解决办法 用递归枚举解决与利润无关背包问题 不是自己创作 文件中的函数名称和简单功能描述: Cbeibao1_0::input():输入关于背包问题的数据信息(背包总重量total_weight,物品件数number, ...
贪心算法 背包问题 c语言 绝对无误 运行成功
背包问题(Knapsack problem)是组合优化领域的一类经典问题: 给定一个物品集合,每个物品具有一定重量以及一定的价值. 对于一个承载重量有限的背包,如何决定放入的物品,使得在背包承载的范围内获取所装物品的最大...
0-1背包问题测试数据,内含多组测试数据,物品的价值量及其重量,复制粘贴即可使用
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最...
简单的遗传算法用于解决背包问题codeblocks编写,运行成功
【背包问题】基于遗传算法求解多背包问题matlab源码
背包问题,算法的背包问题 背包问题,算法的背包问题 背包问题,算法的背包问题
C语言数据结构经典作业 背包问题求解 用栈与非递归算法实现的
此文章讲述了经典的背包问题,以及各种背包问题的变种,是学习算法比较好的东西,也有助于学习各种思想,进一步提高我们解决问题的能力
功能:用贪婪法解决连续背包问题 文件中的函数名称和简单功能描述: Cbeibao2::input():输入关于背包问题的数据信息(背包总重量total_weight,物品件数number, 及每个物品的重量和价值),并为成员指针...
第一讲 01背包问题 这是最基本的背包问题,每个物品最多只能放一次。 第二讲 完全背包问题 第二个基本的背包问题模型,每种物品可以放无限多次。 第三讲 多重背包问题 每种物品有一个固定的次数上限。 第四讲 ...
背包问题: 01背包问题 02: 完全背包问题 03: 多重背包问题 04: 混合三种背包问题 05: 二维费用的背包问题 06: 分组的背包问题 07: 有依赖的背包问题 08: 泛化物品 09: 背包问题问法的变化 11: 背包问题的搜索解法
与0-1背包问题类似,所不同的是在选择物品i装入背包时,可以选择物品i的一部分,而不一定要全部装入背包,1≤i≤n。
用禁忌搜索算法求解背包问题。假设背包容量一定,已知每种物品的体积和价值,求出使价值最大的最优解。
主要介绍了Python基于回溯法解决01背包问题,结合实例形式分析了Python回溯法采用深度优先策略搜索解决01背包问题的相关操作技巧,需要的朋友可以参考下
在中国,背包问题一般是这样描述的:设n个重量为(W1,W2,...Wn)的物品和一个载重为S的背包,将物品的一部分xi放进背包中的利润是Pixi,问如何选择物品的种类和数量,使得背包装满而获得最大的利润?另有一简化版本...