背包问题有很多种,简单背包,物品有价值的背包。下面是个有价值背包的代码。很久以前写的。
import java.util.LinkedList; import java.util.List; public class ItemWithWeight { /** * @param args */ private static Item[] items; private static int m = 10; public static void main(String[] args) { init(); Result currentValue = knap(m,items.length-1); System.out.println(currentValue.getCount()); System.out.println(currentValue.getResult()); } private static Result knap(int m,int position) { if (position<0) { // the list contains nothing return new Result(); } int surplus = m - items[position].getWeight(); if (surplus >=0){ //if we choose this one Result choose = knap(surplus, position-1); //put current one in the list choose.addResult(position);choose.addCount(items[position].getValue()); //if we did not choose one Result notChoose = knap(m, position-1); if (choose.getCount() - notChoose.getCount() >= 0) { return choose; } else { return notChoose; } } else { //if the surplus is smaller than 0 //we can not choose this one return knap(m, position-1); } } private static void init() { items = new Item[11]; items[0] = new Item(1,4); items[1] = new Item(2,5); items[2] = new Item(3,12); items[3] = new Item(24,354); items[4] = new Item(5,6); items[5] = new Item(6,22); items[6] = new Item(7,8); items[7] = new Item(8,1); items[8] = new Item(15,200); items[9] = new Item(15,87); items[10] = new Item(30,245); } private static class Item{ public Item(int weight,int value) { this.weight = weight; this.value = value; } int weight; int value; public int getWeight() { return weight; } public void setWeight(int weight) { this.weight = weight; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } @Override public String toString() { return weight+","+value; } } private static class Result{ private List<Integer> result = new LinkedList<Integer>(); private int count = 0; public List<Integer> getResult() { return result; } public void setResult(List<Integer> result) { this.result = result; } public int getCount() { return count; } public void setCount(int count) { this.count = count; } public void addCount(int value) { this.count+=value; } public void addResult(int itemNo) { this.result.add(itemNo); } } }
发表评论
-
ZOJ 1008 Gnome Tetravex
2012-05-15 17:14 1262Hart is engaged in playing an i ... -
ZOJ 1006 Do the Untwist
2012-05-14 13:36 1089真的不知道这个题目。。。有什么意思。。 不想解释了。。 直 ... -
八皇后
2012-05-14 10:23 688八皇后 问题,是一个古老而著名的问题,是回溯算法的典型例题。 ... -
最大字串
2012-05-14 09:53 581字符串的最大子串么 代码比较简单。。直接上吧。大学时期的程序 ... -
汽车加油问题
2012-05-14 09:21 795就是。。经典问题么。。 有很多个加油站,汽车最远跑多少公里, ... -
ZOJ 1005 Jugs
2012-05-11 15:49 743原题地址:http://acm.zju.edu.cn/onli ... -
ZOJ 1004 Anagrams by Stack
2012-05-11 15:35 1103原题:http://acm.zju.edu.cn/online ... -
ZOJ 1003 Crashing Balloon
2012-05-11 15:20 1233原题地址: http://acm.zju.edu.cn/onl ... -
ZOJ 1002 Fire Net
2012-05-11 14:52 1094原题目链接:http://acm.zju.edu.cn/onl ... -
稀烂的算法。。。声明下
2012-05-11 14:17 545放了点算法的东西在这里,我不是什么算法大神。。。 所以 ...
相关推荐
背包问题: 01背包问题 02: 完全背包问题 03: 多重背包问题 04: 混合三种背包问题 05: 二维费用的背包问题 06: 分组的背包问题 07: 有依赖的背包问题 08: 泛化物品 09: 背包问题问法的变化 11: 背包问题的搜索解法
01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下: 给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择...
使用遗传算法解决0-1背包问题,调试成功,非常适合初学者了解遗传算法和0-1背包问题
实验目的: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语言 绝对无误 运行成功
此类问题为背包问题。物品或者装入背包,或者不装入背 包,称之为0/1被包问题 假设xi表示物品i被装入背包的情况,xi = 1表示物品装 入背包,xi = 0表示物品没装入背包,根据题目要求,有 下列约束函数 SUM(wi*xi) ,...
背包问题(Knapsack problem)是组合优化领域的一类经典问题: 给定一个物品集合,每个物品具有一定重量以及一定的价值. 对于一个承载重量有限的背包,如何决定放入的物品,使得在背包承载的范围内获取所装物品的最大...
0-1背包问题测试数据,内含多组测试数据,物品的价值量及其重量,复制粘贴即可使用
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最...
简单的遗传算法用于解决背包问题codeblocks编写,运行成功
【背包问题】基于遗传算法求解多背包问题matlab源码
背包问题,算法的背包问题 背包问题,算法的背包问题 背包问题,算法的背包问题
C语言数据结构经典作业 背包问题求解 用栈与非递归算法实现的
此文章讲述了经典的背包问题,以及各种背包问题的变种,是学习算法比较好的东西,也有助于学习各种思想,进一步提高我们解决问题的能力
功能:用贪婪法解决连续背包问题 文件中的函数名称和简单功能描述: Cbeibao2::input():输入关于背包问题的数据信息(背包总重量total_weight,物品件数number, 及每个物品的重量和价值),并为成员指针...
第一讲 01背包问题 这是最基本的背包问题,每个物品最多只能放一次。 第二讲 完全背包问题 第二个基本的背包问题模型,每种物品可以放无限多次。 第三讲 多重背包问题 每种物品有一个固定的次数上限。 第四讲 ...
贪心法证明背包问题: 个最优解。 证明基本思想:通过将贪心法的解与任何最优解进行比较来证明。如果这两个解不同,就找出不相等的且下标最小的第一个,从中可推出与假设矛盾的结论。 证明:设X=(x1,…xn)是...
与0-1背包问题类似,所不同的是在选择物品i装入背包时,可以选择物品i的一部分,而不一定要全部装入背包,1≤i≤n。