- android - 多次调用 OnPrimaryClipChangedListener
- android - 无法更新 RecyclerView 中的 TextView 字段
- android.database.CursorIndexOutOfBoundsException : Index 0 requested, 光标大小为 0
- android - 使用 AppCompat 时,我们是否需要明确指定其 UI 组件(Spinner、EditText)颜色
我正在尝试编写一个程序,该程序按顺序读取书籍,将它们存储在堆中,并实现贪婪算法,根据重量将书籍有效地装入盒子中;
我在正确实现堆时遇到问题。
我用来添加到堆的方法称为 addLastChild()。它应该找到堆中的下一个位置并插入新书并根据其重量进行重组。
这是添加代码:
public void addLastChild(Book newBook)
{
Book[] pathList = new Book[30];
int tracker = 0;
int cnt = BookCnt+1;
String path = "";
while(cnt >= 1)
{
path = (cnt %2) + path;
cnt = cnt / 2;
}
Book c = root;
if(root!=null)
{
pathList[tracker]=root;
tracker++;
}
for(int i = 1; i < path.length()-1; i++){
if(path.charAt(i)== '0') {
c = c.left;
pathList[tracker]=c;
tracker++;
} else {
c = c.right;
pathList[tracker]=c;
tracker++;
}
}
if(path.length() == 1)
{
root = newBook;
}
else if(path.charAt(path.length()-1)== '0') {
c.left = newBook;
pathList[tracker]=c.left;
tracker++;
}
else
{
c.right = newBook;
pathList[tracker]=c.right;
tracker++;
}
BookCnt++;
boolean doTrickle = false;
if(tracker>=2)
{
doTrickle = true;
}
while(doTrickle == true)
{
Book temp = new Book(pathList[tracker-2].refNumber, pathList[tracker-2].weight, pathList[tracker-2].title, null,null);
//int refNumber, int weight, String title, Book left, Book right
print(root," ");
if(pathList[tracker-1].weight > pathList[tracker-2].weight)
{
pathList[tracker-2].refNumber=pathList[tracker-1].refNumber;
pathList[tracker-2].title=pathList[tracker-1].title;
pathList[tracker-2].weight=pathList[tracker-1].weight;
if(pathList[tracker-2].left == pathList[tracker-1])
{
pathList[tracker-2].left = temp;
}
if(pathList[tracker-2].right == pathList[tracker-1])
{
pathList[tracker-2].right = temp;
}
tracker--;
System.out.println("we trickled");
print(root," ");
}
else
{
doTrickle =false;
}
}
}
我用来从堆中删除的两个方法是removeLastChild()和remove(),removeLastChild()方法返回堆中的最后一本书,而remove()应该返回权重最大的书,并用最后一本书替换根,然后相应地重组堆。
这是给我带来麻烦的删除代码:
Book removeLastChild() {
int cnt = BookCnt;
String path = "";
while(cnt >= 1)
{
path = (cnt %2) + path;
cnt = cnt / 2;
}
Book returnBook = null;
Book c = root;
for(int i = 1; i < path.length()-1; i++){
if(path.charAt(i)== '0') {
c = c.left;
} else {
c = c.right;
}
}
if(path.length() == 1)
{
returnBook = root;
root = null;
}
else if(path.charAt(path.length()-1)== '0') {
returnBook = c.left;
c.left = null;
}
else
{
returnBook = c.right;
c.right = null;
}
BookCnt--;
return returnBook;
}
Book remove()
{
Book largest =root;
root = removeLastChild();
if(largest.left!= null)
{
root.left = largest.left;
}
if(largest.right!= null)
{
root.right = largest.right;
}
Book cur = root;
if(root!= null)
{
while(cur.left !=null && cur.right!= null)
{
if(cur.weight<cur.left.weight || cur.weight<cur.right.weight)
{
Book temp = new Book(cur.refNumber, cur.weight, cur.title, null, null);
//int refNumber, int weight, String title, Book left, Book right
if(cur.left.weight>cur.right.weight)
{
cur.refNumber = cur.left.refNumber;
cur.title = cur.left.title;
cur.weight = cur.left.weight;
cur.left.refNumber = temp.refNumber;
cur.left.weight = temp.weight;
cur.left.title = temp.title;
cur = cur.left;
}
else
{
cur.refNumber = cur.right.refNumber;
cur.title = cur.right.title;
cur.weight = cur.right.weight;
cur.right.refNumber = temp.refNumber;
cur.right.weight = temp.weight;
cur.right.title = temp.title;
cur = cur.right;
}
}
else
{
return largest;
}
}
}
return largest;
}
感谢您的帮助!
我很乐意澄清任何我没有明确传达的内容。
最佳答案
如果我可以建议您的堆实现的替代方案,并考虑到您对背包问题的贪婪算法的目标,为什么不简单地使用 PriorityQueue ?
来自文档:“基于优先级堆的无界优先级队列。优先级队列的元素根据其自然顺序进行排序,或者通过在队列构造时提供的比较器进行排序(...)”
如果您的书籍类实现了这样的 Comparable 接口(interface)(示例中的 Book 非常简化):
class Book implements Comparable<Book>{
public String title;
public int weight;
public Book(int weight, String title) {
this.weight = weight;
this.title = title;
}
@Override
public int compareTo(Book anotherBook) {
return weight - anotherBook.weight;
}
}
书籍的自然排序应该是从权重最小的书到权重最大的书。
在优先级队列中使用 Book 类:
public static void main(String[] args) {
Book book1 = new Book(10,"a");
Book book2 = new Book(11,"b");
Book book3 = new Book(20,"c");
Book book4 = new Book(20,"d");
Book book5 = new Book(11,"e");
PriorityQueue<Book> bookQueue = new PriorityQueue<Book>();
bookQueue.add(book1);
bookQueue.add(book2);
bookQueue.add(book3);
bookQueue.add(book4);
bookQueue.add(book5);
while(!bookQueue.isEmpty()){
Book book = bookQueue.poll();
System.out.println(book.title + " - " + book.weight);
}
}
您应该能够按照将书籍放入盒子中所需的方式迭代这些书籍。
关于java - 堆书盒包装,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8107012/
正在尝试创建一个 python 包。似乎有效,但我收到警告。我的 setup.py 是: #! /usr/bin/env python from distutils.core import setup
我导入了一个数据类型 X ,定义为 data X a = X a 在本地,我定义了一个通用量化的数据类型,Y type Y = forall a. X a 现在我需要定义两个函数, toY 和 fro
我似乎无法让编译器让我包装 Tokio AsyncRead: use std::io::Result; use core::pin::Pin; use core::task::{Context, Po
我有两个函数“a”和“b”。当用户上传文件时,“b”被调用。 “b”重命名文件并返回新文件名。之后应该编辑该文件。像这样: def a(): edits file def b(): r
我使用 Entity Framework 作为我的 ORM,我的每个类都实现了一个接口(interface),该接口(interface)基本上表示表结构(每个字段一个只读属性)。这些接口(inter
有没有办法打开一个程序,通常会打开一个新的jframe,进入一个现有的jframe? 这里是解释,我下载了一个java游戏,其中一个是反射游戏,它在一个jframe中打开,框架内有一堆子面板,我想要做
我想要下面的布局 | AA BBBBBBB | 除非没有足够的空间,在这种情况下 | AA | | BBBBBBB | 在这种情况下,A 是复选框,B 是复选框旁边的 Text
我正在尝试以不同的方式包装我的网站,以便将背景分为 2 部分。灰色部分是主要背景,还有白色部分,它较小并包装主要内容。 基本上我想要this看起来像this . 我不太确定如何添加图像来创建阴影效果,
我正在使用 : 读取整数文件 int len = (int)(new File(file).length()); FileInputStream fis = new FileInputStream(f
我使用 maven 和 OpenJDK 1.8 打包了一个 JavaFX 应用程序我的 pom.xml 中的相关部分: maven-assembly-plugin
我正在使用两个不同的 ItemsControl 来生成一个按钮列表。
我有一个情况,有一个变量会很方便,to , 可以是 TimerOutput或 nothing .我有兴趣提供一个采用与 @timeit 相同参数的宏来自 TimerOutputs(例如 @timeit
我正在尝试包装一个名为 content 的 div与另一个具有不同背景的 div。 但是,当将“margin-top”与 content 一起使用时div,似乎包装 DIV 获得了边距顶部而不是 co
文档不清楚,它似乎允许包装 dll 和 csproj 以在 Asp.Net Core 5 应用程序中使用。它是否允许您在 .Net Core 5 网站中使用针对 .Net Framework 4.6
我被要求开发一个层,该层将充当通用总线,而不直接引用 NServiceBus。到目前为止,由于支持不引人注目的消息,这并不太难。除了现在,我被要求为 IHandleMessages 提供我们自己的定义
我正在尝试包装 getServersideProps使用身份验证处理程序函数,但不断收到此错误:TypeError: getServerSideProps is not a function我的包装看
我有一个项目,它在特定位置(不是/src/resources)包含资源(模板文件)。我希望在运行 package-bin 时将这些资源打包。 我看到了 package-options 和 packag
我正在寻找打印从一系列对象中绘制的 div。我可以通过使用下面的管道语法来实现这一点。 each i, key in faq if (key == 0) |
我在 Meteor.js“main.js - Server”中有这个方法。 Meteor.methods({ messageSent: function (message) { var a
我注意到,如果我的自定义Polymer 1.x元素的宽度比纸张输入元素上的验证错误消息的宽度窄,那么错误将超出自定义元素的右边界。参见下图: 有没有一种机制可以防止溢出,例如在到达自定义元素的边界时自
我是一名优秀的程序员,十分优秀!