import java.util.Vector;
public class PackageTest {
/**
* 背包算法:最优化问题,为一个给定空间或负重的背包和许多大小不一的物体分配适合的空间
* 哪些物体放入背包才能使得浪费的背包空间或负重最小?
* 在背包很小和物体数目较少时,这个问题还比较容易解决,但当背包很大且有很多个物体时,
* 问题的求解就十分困难,通常这个问题会有一个或多个解,也有可能根本没有解。。。。
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]={11,8,7,6,5};
int b[]={13,8,7,6,5};
int total=20;
int leftbound=total;
int max=0;
int i=0;
int j=0;
Vector v1=new Vector();
Vector v2=new Vector();
while(j<5){
i=j;
while(i<5){
if(a[i]<=leftbound){
v1.addElement(new Integer(a[i]));
v2.addElement(new Integer(i));
}
if(i>=4 && !v1.isEmpty()){
int value=0;
for(int k=0;k<v1.size();k++){
System.out.print(((Integer)v1.elementAt(k)).intValue());
System.out.print(",");
value=value+b[((Integer)v2.elementAt(k)).intValue()];
}
System.out.println("value="+value);
if(max<value){
max=value;
}
leftbound=leftbound+((Integer)v1.remove(v1.size()-1)).intValue();
i=((Integer)v2.remove(v2.size()-1)).intValue()+1;
continue;
}
i++;
}
j++;
leftbound=total;
int value=0;
for(int k=0;k<v1.size();k++){
System.out.println((Integer)v1.elementAt(k));
System.out.println(",");
value=value+b[((Integer)v2.elementAt(k)).intValue()];
}
System.out.println("value="+value);
if(max<value){
max=value;
}
while(!v1.isEmpty()){
v1.remove(v1.size()-1);
v2.remove(v2.size()-1);
}
}
System.out.println("max="+max);
}
}
分享到:
相关推荐
原先在网上找到某位大虾写的一个简单的背包算法,于是在其基础上改成适合我们目前项目中要求的背包算法。此算法要求传入一组对象集合(其中的对象中只包含主键和值)和某个条件值,然后能打印sum(对象.值)条件的1个...
背包算法 背包算法JAVA实现 背包算法JAVA实现
基于0-1背包算法的社交网络行为隐写术.docx
分支界限思想解0-1背包算法
C++编写的背包算法程序 cpp 动态规划
背包算法规划求解,解决问题场景如:售货架中有n种商品(每种商品只有一个),给定200块钱购物,尽可能的购买到更多的商品,将这本金最大化利用。
用 PHP 实现的 01 背包算法,参考了网上的相关 C++ 算法,用来方便 PHP 程序员改造使用,我是用它来实现在指定宽度的栏中整齐的排列一堆标签云,效果非凡且神奇,初次使用时一瞬间的确有这样的感觉。
讲诉的是背包算法在matlab下的实现以及背包算法的性能
背包 背包问题 背包算法 背包 noip 竞赛 信息技术 基础算法
0-1背包算法代码实现,用c++实现,可以运行,希望可以给您带来帮助。
对各种背包问题的详解,01背包,多重背包等等
输入物品数量n,报的容量m,每个物品的体积,每个物品的价值 输入:最大价值
01背包问题算法 动态规划 代码 01背包问题算法 动态规划 代码 01背包问题算法 动态规划 代码
0-1背包问题动态规划实现,部分背包问题使用了贪心算法。
、用自底向上的动态规划算法解决背包问题。测试数据如下: 物品(1,2,3,4,5),重量(3,2,1,4,5),价值(25,20,15,40,50)。承重量W=6。 求解最佳子集。
使用遗传算法解决0-1背包问题,调试成功,非常适合初学者了解遗传算法和0-1背包问题
这个是背包算法。。解决背包问题的java代码。。。。。。。。。。。。。。。。。。。。。。
用C实现的关于密码学编程的背包算法,自有有效
回溯算法 0-1 背包算法 C++ 代码
C++代码实现回溯算法 0 1 背包算法