java – 打印输出0/1 KnapSack(递归蛮力)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java – 打印输出0/1 KnapSack(递归蛮力),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1557字,纯文字阅读大概需要3分钟。
内容图文
![java – 打印输出0/1 KnapSack(递归蛮力)](/upload/InfoBanner/zyjiaocheng/827/08c7951c4ebd4e4eb3eb58bb096312dc.jpg)
public static int KnapSack(int capacity, Item[] items, int numItems) {
if (numItems == 0 || capacity == 0)
return 0;
if (items[numItems-1].weight > capacity)
return KnapSack(capacity, items, numItems-1);
else {
int took = items[numItems-1].value + KnapSack(capacity - items[numItems-1].weight, items, numItems-1);
int left = KnapSack(capacity, items, numItems-1);
return Math.max(took, left);
}
}
所以我有一个工作的0/1递归强力算法为KnapSack问题工作.我想知道打印出工作解决方案的方法是什么(即从项目集中收集到背包里的物品).我已经尝试了很多东西,例如添加到列表中并尝试跟踪我添加的内容,但是没有一个可以解决实现或设计问题.所以我来这里寻求帮助,谢谢!
解决方法:
要跟踪拍摄的项目,请尝试以下操作:
public static int KnapSack(int capacity, Item[] items, int numItems, ArrayList<Integer> taken) {
if (numItems == 0 || capacity == 0)
return 0;
if (items[numItems-1].weight > capacity)
return KnapSack(capacity, items, numItems-1, taken);
else {
final int preTookSize = taken.size();
final int took = items[numItems-1].value + KnapSack(capacity - items[numItems-1].weight, items, numItems-1, taken);
final int preLeftSize = taken.size();
final int left = KnapSack(capacity, items, numItems-1, taken);
if (took > left) {
if (taken.size() > preLeftSize)
taken.removeRange(preLeftSize, taken.size());
taken.add(Integer.valueOf(numItems - 1));
return took;
}
else {
if (preLeftSize > preTookSize)
taken.removeRange(preTookSize, preLeftSize);
return left;
}
}
}
这可能不是最有效的,但我认为它应该有效.
(为了提高效率,您可以尝试将所采用的ArrayList预先分配为“足够大”,以便在递归循环期间不需要进行分配.)
内容总结
以上是互联网集市为您收集整理的java – 打印输出0/1 KnapSack(递归蛮力)全部内容,希望文章能够帮你解决java – 打印输出0/1 KnapSack(递归蛮力)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。