背包问题有许多种形式,最简单的背包问题形式:现在有一堆石头,(比如重量为2,6,8,10),一个背包中可以装指定的重量(比如14)的石头,请问背包中可以放入的石头的组合。
代码中假设石头是个源数组,背包是目标数组。
算法中使用分治的想法将此问题递归为两个小范围的问题。
针对第n个石头,背包问题可以分解为两种组合的何:含第n个石头的背包的组合,与不含n个石头的背包的组合,
1.假设含第n个石头,背包问题变为,针对剩下的石头求得总重量减去第n个石头的重量的背包问题。
2.不含n个石头,背包问题变为针对剩下的石头求得总重量的背包问题。
class Bag {
public static void main(String[] args) {
int[] src = {2,4,5,7,8,6,10};
select(14,src, 0, new int[src.length]);
}
/**
* @param total 总数
* @param src 源数据数组
* @param offset 源数组的起始位置
* @param bag 背包,装选中的数据
*/
private static void select(int total, int [] src, int offset, int[] bag) {
if(total == 0) { //背包要求增加的重量为0,则直接打印背包
print(bag);
return;
}
//从起始值开始寻找第一个小于要求增加重量的数值
while(offset < src.length && total < src[offset]) offset++;
if(offset >= src.length) return; //当没有源数据可以选择,则退出
//将问题化简为在剩下的源数据中,两个找到重量的问题
select(total,src,offset+1,bag.clone()); //背包中含有offset位置的
select(total-src[offset],src,offset+1,put(bag,src[offset]));//背包中不含有offset位置的
}
private static int[] put(int[] bag, int n) { //将数字放入背包中
int pos = -1;
while(bag[++pos] > 0); //找到背包中第一个数字为0的位置
bag[pos] = n;
return bag;
}
private static void print(int[] bag) { //打印背包中的数字
System.out.print("bag: ");
for(int n: bag) {
if(n == 0) break;
System.out.print(n + " ");
}
System.out.println();
}
}
分享到:
相关推荐
基于于C++的使用递归的方式解0-1背包
回溯递归解决背包问题 int temp_c,i,total_weight,num,j=0,result[1000],total_value; scanf("%d%d",#,&temp;_c); while(num!=0||temp_c!=0) { total_value=0; total_weight=0; for(i=0;i;++i) { a[i]...
0-1背包问题 递归算法 c语言实现,已通过编译,可以直接使用
C++ 动态规划算法实现0-1背包问题 包含了代码、算法分析、测试文件和结果,非常详尽,值得拥有!
本资源包括0-1背包问题的算法分文档析和Java源代码,Eclipse环境下运行正确。
自己写的用递归实现的背包问题,欢迎各位高手指正。
使用动态规划方法实现0/1背包问题求解;一共两种解法:存储记忆+递归; 自下而上的递归(迭代法);我CSDN博客有详细介绍。
背包问题递归算法 C的源代码~~ 希望能够对大家有帮助哦·
全都是自己写的,都能跑出来 实打实写的哦~ 仅供参考 最重要的还是自己理解 1.学习并掌握回溯法 2.利用迭代回溯和递归回溯两种方法解决01背包问题。 预览地址:
主要介绍了python基于递归解决背包问题,递归是个好东西,任何具有递归性质的问题通过函数递归调用会变得很简单。一个很复杂的问题,几行代码就能搞定,需要的朋友可以参考下
利用了递归调用,将经典的背包问题简单方便的得以实现。
背包问题递归实现C++
关于0-1背包问题的c语言代码,文本文档的,只是代码,已经调试好了,可以直接复制到vc环境中运行,里面有相应解释,如大家想让其在运行后在决定背包容量和物品数量,请用链表改进后实现
非常有用的背包问题动态规划递归算法,计算机老师强烈推荐
用递归枚举解决与利润无关背包问题 不是自己创作 文件中的函数名称和简单功能描述: Cbeibao1_0::input():输入关于背包问题的数据信息(背包总重量total_weight,物品件数number, 及每个物品的重量),并为...
实现了计算随机生成的背包容量和物品价值,重量的0-1背包问题的动态规划算法
背包问题的递归算法,很好 问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。
算法分析与设计 回溯法 背包问题 递归与迭代
01背包问题 课程作业 文件读入 文件输出 直接可用
改算法实现了简单背包问题(非递归的),呵呵 随手写的 忘各位大虾给小弟看下 谢谢