热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

Hashtable的已在元素无法找到的问题

这个问题是在做这道习题时出现的:3-20商店中每种商品都有标价。例如,一朵花的价格是2元,一个花瓶的价格是5元。为了吸引顾客,商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一组,并降价销
这个问题是在做这道习题时出现的:
3-20 商店中每种商品都有标价。例如,一朵花的价格是2元,一个花瓶的价格是5元。为了吸引顾客,商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一组,并降价销售。例如,3朵花的价格不是6元而是5元。2个花瓶加1朵花的优惠价是10元。试设计一个算法,计算出某一个顾客所购商品应付的最少费用。

这是王晓东《计算机算法设计与分析》一书第3章动态规划里的一道课后习题。习题本身比较简单,主要涉及的算法是备忘录方法。我关键想问的是 我实现算法过程中所用的Hashtable出现的找不到已在元素的问题,我在类中已经重载了Hashcode(),以及equals()。
这个程序,涉及到两个输入文件,一个是商品列表merchandise,一个是优惠策略policy。也即有多少种商品及其单价,和,怎样的商品组合的优惠价格是多少,这些信息是动态输入的。
程序根据,举个例子,比如设定好3种商品,以及3条优惠策略,那么可知对于用户购买要求(a,b,c)--0商品a件,1商品b件,2商品c件,它的求解递归式是:
Cost(a,b,c)=min{ Cost(a-x,b-y,c-z)+totalPrice(x,y,z) }
其中,(x,y,z)是任一条优惠策略(为统一处理单买的情况,将单买也作为一条优惠策略),totalPrice为该条策略的总价。如果a-x<0就置为0,其余类似。思想便是通过策略降低问题规模动规求解。
因为不知道商品有多少种,因而cost矩阵的维数不能事先确定。但我们所要的只是在计算未知请求时降低规模后,能够给出已经计算出的小规模请求的最优耗费,所以可以采用以请求向量,如上例子中的(a,b,c)作为key值,Cost(a,b,c)作为value的Hashtable来存储已经计算得到的值,用备忘录方法实现。
具体不再介绍了。进入正题,郁闷的是,我用Hashtable来存储cost值时,明明已经加入到Hashtable的请求向量却在需要时无法得到,比如(1,1,1)已经算过,因而加入到了Hashtable中,下次在算(1,2,1)时利用某策略后比如降为(1,1,1)后检查是否已经计算(已计算直接返回而不需计算),竟然找不到!有时其他情况却又可以找到。后来无奈,自己写了一个可以按需设定维数的可变维数组(一维分段实现多维)代替Hashtable,结果没有问题。
所以总结一下问题,java的Hashtable为何会找不到已在的元素,在类中已经重载了Hashcode(),以及equals()。。应该是我的程序的问题,但是用自己写的多维数组类代替Hashtable在程序中的用途,程序又没有问题。所以还请各位java高人热心指点!万分感谢!
这是一个300行的小程序。我把两个实现(Hashtable、多维数组类)都放在上面,以做对比。商品信息的数据由文件读入,用户请求界面输入。还请高手们不厌其烦,看看代码,帮帮在下。感谢感谢!

先将两个输入文件的结构展示如下:

文件merchandise.txt

total ----总的商品个数
price[0]---id=0 的商品价格
price[1]---id=1 
.
.
price[total-1]

文件policy.txt

total ----策略条数
maxRefer---每条策略最多涉及的商品种数
referNum id num[id] ... id num[id] totalPrice
--该条策略涉及的商品种数 id 需要购买id商品的个数... 总和价格(应当比单买便宜)

示例文件数据如下:

文件merchandise.txt
3
2
5
9

文件policy.txt

3
3
2 0 1 1 2 10
2 1 2 2 1 6
3 0 1 1 1 2 1 11

运行过程中的用户购买请求输入示例:
3
0 1 --id=0商品购买1件
1 3 --id=1...   3
2 2 --id=2...   2

附上程序如下:---因为不允许贴子内容太长,请继续看
Hashtable的已在元素无法找到的问题1

6 个解决方案

#1


太长了。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

#2


谢谢大家的耐心哈
谢谢...

#3


注意一下好吗,我把程序还是写在回复里吧

有问题的Hashtable实现方式:

import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Hashtable;
import java.lang.Float;
//import java.io.FileOutputStream;
import java.io.RandomAccessFile;
class Policy{
int refer;
int inPair[][];
int cur;
float totalPrice;
Policy(int refer){
this.refer=refer;
cur=0;
inPair=new int[refer][2];
}
public void setNextInPair(int id,int num){
inPair[cur][0]=id;
inPair[cur][1]=num;
cur++;
}
public void setTotalPrice(float price){
totalPrice=price;
}
public float getTotalPrice(){
return totalPrice;
}
}
class Query{
int refer;
int num[];
Query(int totalKinds){
this(totalKinds,false);
}
Query(Query a){
refer=a.refer;
num=new int[a.num.length];
for(int i=0;i num[i]=a.num[i];
}
}
Query(int totalKinds,boolean isEmpty){
init(totalKinds);
if(!isEmpty){
Scanner scanner=new Scanner(System.in);
System.out.print("How many kinds merchandise would you buy: ");
if(scanner.hasNextInt())
refer=scanner.nextInt();
else
java.lang.Runtime.getRuntime().exit(0);
System.out.println("id\tnum");
for(int i=0;i num[scanner.nextInt()]=scanner.nextInt();
}
}
}
void init(int totalKinds){
refer=0;
num=new int[totalKinds];
for(int i=0;i num[i]=0;
}
public void printQuery(RandomAccessFile fileOut)throws Exception{
fileOut.writeChar('(');
for(int i=0;i {
fileOut.writeChars(new Integer(num[i]).toString());
if(i!=num.length-1)
fileOut.writeChar(',');
else{
fileOut.writeChar(')');
// fileOut.writeChar('\r');
fileOut.writeChar('\n');
}
}
}
public void  reset(Query a){
refer=a.refer;
for(int i=0;i num[i]=a.num[i];
}
public boolean equals(Object obj){
return equals((Query)obj);
}
public boolean equals(Query a){
if(refer!=a.refer) return false;
for(int i=0;i if(num[i]!=a.num[i]) return false;
}
return true;
}
public int hashCode(){
final int P=37;
final int MAX=483647;
int rtn=1;
for(int i=0;i if(num[i]>0)
rtn=(rtn*P+num[i]*i)%MAX;
}
return rtn;
}
/*
public int hashCode(){
String s=new String();
final String insert="37";
for(int i=0;i s=s+num[i]+insert;
}
return s.hashCode();
}*/
}
public class CommercialPromotion {
float merchandise[];
Policy policies[];
int pNum;
Hashtable cost;
CommercialPromotion(String mfName,String pfName){
init(mfName,pfName);
}
CommercialPromotion(){
Scanner scanner=new Scanner(System.in);
System.out.println("Input the merchandise file's name: ");
System.out.println("and the policy file's name: ");
init(scanner.next(),scanner.next());
}
void init(String mfName,String pfName){
Scanner mScanner;
Scanner pScanner;
int t0,t1,i,j,k;
try{
mScanner=new Scanner(new File(mfName));
pScanner=new Scanner(new File(pfName));

t0=mScanner.nextInt();
merchandise=new float[t0];
for(i=0;i merchandise[i]=mScanner.nextFloat();
}
t1=pScanner.nextInt();
pNum=t1;//
policies=new Policy[t0+t1];//
pScanner.nextInt();
for(i=0;i k=pScanner.nextInt();
policies[i]=new Policy(k);
for(j=0;j policies[i].setNextInPair(pScanner.nextInt(),pScanner.nextInt());
}
policies[i].setTotalPrice(pScanner.nextFloat());
}
for(t1=t0+t1,j=0;i policies[i]=new Policy(1);
policies[i].setNextInPair(j,1);
policies[i].setTotalPrice(merchandise[j]);
}
}catch(FileNotFoundException e){
System.out.println(e);
}
cost=new Hashtable();
cost.put(new Query(merchandise.length,true),new Float(0));
}

//买多了或许更便宜
boolean executePolicy(Query q,int p){
float tmp=getSimpleTotalCost(q);
Query q0=new Query(q);
if(tmp<=policies[p].getTotalPrice())
return false;//如果选择了优惠方案p反而它的总价比全部单买还贵,不如不选
for(int i=0;i q.num[policies[p].inPair[i][0]]-=policies[p].inPair[i][1];
if(q.num[policies[p].inPair[i][0]]<=0){
if(q.num[policies[p].inPair[i][0]]>-policies[p].inPair[i][1])
q.refer--;
q.num[policies[p].inPair[i][0]]=0;
}
}
if(q0.equals(q))
return false;
return true;
}
float getSimpleTotalCost(Query q){
float rtn=0;
for(int i=0;i if(q.num[i]!=0)
rtn+=merchandise[i]*q.num[i];
}
return rtn;
}
RandomAccessFile fileOut;//debug
int cn;//debug
float getCost(Query q){
Float rtn;
rtn=cost.get(q);
cn++;//debug
try{//debug
q.printQuery(fileOut);
}catch(Exception e){}
if(rtn!=null)
return rtn.floatValue();
rtn=new Float(getSimpleTotalCost(q));
Query tmp=new Query(q);
float f;
for(int i=0;i if(executePolicy(tmp,i)){
f=getCost(tmp)+policies[i].getTotalPrice();
if(rtn.floatValue()>f)
rtn=Float.valueOf(f);
}
tmp.reset(q);//tmp=q;wrong : tmp=q相当于使tmp指向了p//revert
}
cost.put(q,rtn);
return rtn.floatValue();
}
void show(Query q){
int pn[]=new int[policies.length];
for(int i=0;i Float f0=cost.get(q);
Float f1;
if(f0==null)return ;
Query q0=new Query(q);
Query q1=new Query(q);
for(int i=0;i if(executePolicy(q1,i)){
f1=cost.get(q1);
if(f1!=null&&f0.equals(f1+policies[i].getTotalPrice())){
pn[i]++;
i--;//
q0.reset(q1);
f0=f1;
}else
q1.reset(q0);//revent
}else
q1.reset(q0);//revent
}
for(int i=0,j=pNum;i if(q1.num[i]>0)
pn[j]=q1.num[i];
}
boolean first=true;
for(int i=0;i if(pn[i]!=0){
if(first){
first=false;
System.out.print(getCost(q)+" = ");
}else
System.out.print(" + ");
if(i System.out.print("p_"+i+"_"+policies[i].getTotalPrice()+" * "+pn[i]);
}else
System.out.print("m_"+(i-pNum)+"_"+policies[i].getTotalPrice()+" * "+pn[i]);
}
}
System.out.println();
}
public static void main(String args[]){
CommercialPromotion example;
if(args.length==2)
example=new CommercialPromotion(args[0],args[1]);
else
example=new CommercialPromotion();
Query q;
try{example.fileOut=new RandomAccessFile("outFile.txt","rw");}catch(Exception e){}//debug
while(true){
q=new Query(example.merchandise.length);
System.out.print("The total price is : ");
example.cn=0;//debug
System.out.println(example.getCost(q));
System.out.println("(After : "+example.cn+" )");//debug
example.show(q);
}
}
}

#4


没有问题的多维数组实现方式,其他实现与上面一摸一样:

import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.RandomAccessFile;

class Policy{
int refer;
int inPair[][];
int cur;
float totalPrice;
Policy(int refer){
this.refer=refer;
cur=0;
inPair=new int[refer][2];
}
public void setNextInPair(int id,int num){
inPair[cur][0]=id;
inPair[cur][1]=num;
cur++;
}
public void setTotalPrice(float price){
totalPrice=price;
}
public float getTotalPrice(){
return totalPrice;
}
}
class Query{
int refer;
int num[];
Query(int totalKinds){
this(totalKinds,false);
}
Query(Query a){
refer=a.refer;
num=new int[a.num.length];
for(int i=0;i num[i]=a.num[i];
}
}
Query(int totalKinds,boolean isEmpty){
init(totalKinds);
if(!isEmpty){
Scanner scanner=new Scanner(System.in);
System.out.print("How many kinds merchandise would you buy: ");
if(scanner.hasNextInt())
refer=scanner.nextInt();
else
java.lang.Runtime.getRuntime().exit(0);
System.out.println("id\tnum");
for(int i=0;i num[scanner.nextInt()]=scanner.nextInt();
}
}
}
void init(int totalKinds){
refer=0;
num=new int[totalKinds];
for(int i=0;i num[i]=0;
}
public void printQuery(RandomAccessFile fileOut)throws Exception{
fileOut.writeChar('(');
for(int i=0;i {
fileOut.writeChars(new Integer(num[i]).toString());
if(i!=num.length-1)
fileOut.writeChar(',');
else{
fileOut.writeChar(')');
// fileOut.writeChar('\r');
fileOut.writeChar('\n');
}
}
}
public void  reset(Query a){
refer=a.refer;
for(int i=0;i num[i]=a.num[i];
}
public boolean equals(Object obj){
return equals((Query)obj);
}
public boolean equals(Query a){
if(refer!=a.refer) return false;
for(int i=0;i if(num[i]!=a.num[i]) return false;
}
return true;
}
/*
public int hashCode(){
final int P=37;
final int MAX=483647;
int rtn=1;
for(int i=0;i if(num[i]>0)
rtn=(rtn*P+num[i]*i)%MAX;
}
return rtn;
}

public int hashCode(){
String s=new String();
final String insert="37";
for(int i=0;i s=s+num[i]+insert;
}
return s.hashCode();
}*/
}
class NDArray{
int MAX=10;
int n;
float v[];
NDArray(int n){
init(n);
}
int getLength(int n){
int rtn=MAX;
for(int i=n;i>1;i--){
rtn*=MAX;
}
return rtn;
}
void init(int n){
this.n=getLength(n);
v=new float[this.n];
for(int i=0;i v[i]=-1;
}
int getPosition(Query q){
int p=0;
for(int i=q.num.length-1;i>=0;i--)
{
p=p*MAX+q.num[i];
}
return p;
}

public void put(Query q,float f){
v[getPosition(q)]=f;
}
public float get(Query q){
return v[getPosition(q)];
}
}
public class CommercialPromotion {
float merchandise[];
Policy policies[];
int pNum;
NDArray cost;
CommercialPromotion(String mfName,String pfName){
init(mfName,pfName);
}
CommercialPromotion(){
Scanner scanner=new Scanner(System.in);
System.out.println("Input the merchandise file's name: ");
System.out.println("and the policy file's name: ");
init(scanner.next(),scanner.next());
}
void init(String mfName,String pfName){
Scanner mScanner;
Scanner pScanner;
int t0,t1,i,j,k;
try{
mScanner=new Scanner(new File(mfName));
pScanner=new Scanner(new File(pfName));

t0=mScanner.nextInt();
merchandise=new float[t0];
for(i=0;i merchandise[i]=mScanner.nextFloat();
}
t1=pScanner.nextInt();
pNum=t1;//
policies=new Policy[t0+t1];//
pScanner.nextInt();
for(i=0;i k=pScanner.nextInt();
policies[i]=new Policy(k);
for(j=0;j policies[i].setNextInPair(pScanner.nextInt(),pScanner.nextInt());
}
policies[i].setTotalPrice(pScanner.nextFloat());
}
for(t1=t0+t1,j=0;i policies[i]=new Policy(1);
policies[i].setNextInPair(j,1);
policies[i].setTotalPrice(merchandise[j]);
}
cost=new NDArray(t0);
cost.put(new Query(merchandise.length,true),0);
}catch(FileNotFoundException e){
System.out.println(e);
}
}

//买多了或许更便宜
boolean executePolicy(Query q,int p){
float tmp=getSimpleTotalCost(q);
Query q0=new Query(q);
if(tmp<=policies[p].getTotalPrice())
return false;//如果选择了优惠方案p反而它的总价比全部单买还贵,不如不选
for(int i=0;i q.num[policies[p].inPair[i][0]]-=policies[p].inPair[i][1];
if(q.num[policies[p].inPair[i][0]]<=0){
if(q.num[policies[p].inPair[i][0]]>-policies[p].inPair[i][1])
q.refer--;
q.num[policies[p].inPair[i][0]]=0;
}
}
if(q0.equals(q))
return false;
return true;
}
float getSimpleTotalCost(Query q){
float rtn=0;
for(int i=0;i if(q.num[i]!=0)
rtn+=merchandise[i]*q.num[i];
}
return rtn;
}
RandomAccessFile fileOut;//debug
int cn;//debug
float getCost(Query q){
float rtn;
rtn=cost.get(q);
cn++;//debug
try{//debug
q.printQuery(fileOut);
}catch(Exception e){}
if(rtn>=0)
return rtn;
rtn=getSimpleTotalCost(q);
Query tmp=new Query(q);
float f;
for(int i=0;i if(executePolicy(tmp,i)){
f=getCost(tmp)+policies[i].getTotalPrice();
if(rtn>f)
rtn=f;
}
tmp.reset(q);//tmp=q;wrong : tmp=q相当于使tmp指向了p//revert
}
cost.put(q,rtn);
return rtn;
}
void show(Query q){
int pn[]=new int[policies.length];
for(int i=0;i float f0=cost.get(q);
float f1;
if(f0<0)return ;
Query q0=new Query(q);
Query q1=new Query(q);
for(int i=0;i if(i==3)
i=3;
if(executePolicy(q1,i)){
f1=cost.get(q1);
if(f1>=0&&f0==f1+policies[i].getTotalPrice()){
pn[i]++;//use polocies[i] one more time
i--;//i=0;//
q0.reset(q1);
f0=f1;
}else
q1.reset(q0);//revent
}else
q1.reset(q0);//revent
}
for(int i=0,j=pNum;i if(q1.num[i]>0)
pn[j]=q1.num[i];
}
boolean first=true;
for(int i=0;i if(pn[i]!=0){
if(first){
first=false;
System.out.print(getCost(q)+" = ");
}else
System.out.print(" + ");
if(i System.out.print("p_"+i+"_"+policies[i].getTotalPrice()+" * "+pn[i]);
}else
System.out.print("m_"+(i-pNum)+"_"+policies[i].getTotalPrice()+" * "+pn[i]);
}
}
System.out.println();
}
public static void main(String args[]){
CommercialPromotion example;
if(args.length==2)
example=new CommercialPromotion(args[0],args[1]);
else
example=new CommercialPromotion();
Query q;
try{example.fileOut=new RandomAccessFile("outFile.txt","rw");}catch(Exception e){}//debug
while(true){
q=new Query(example.merchandise.length);
System.out.print("The total price is : ");
example.cn=0;//debug
System.out.println(example.getCost(q));
System.out.println("(After : "+example.cn+" )");//debug
example.show(q);
}
}
}

#5


会不会问问题呀?这么长谁看得完呀!找出核心问题

#6


比旧社会的裹脚布还长。。。

推荐阅读
  • 常用API-Hashtable类及其与HashMap、HashSet的区别转载请表明出处:http:blog.csdn.netu012637501(嵌入式_小J的天空)一、Hashtable&l ... [详细]
  • [大整数乘法] java代码实现
    本文介绍了使用java代码实现大整数乘法的过程,同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率,并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]
  • Android工程师面试准备及设计模式使用场景
    本文介绍了Android工程师面试准备的经验,包括面试流程和重点准备内容。同时,还介绍了建造者模式的使用场景,以及在Android开发中的具体应用。 ... [详细]
  • HashMap的相关问题及其底层数据结构和操作流程
    本文介绍了关于HashMap的相关问题,包括其底层数据结构、JDK1.7和JDK1.8的差异、红黑树的使用、扩容和树化的条件、退化为链表的情况、索引的计算方法、hashcode和hash()方法的作用、数组容量的选择、Put方法的流程以及并发问题下的操作。文章还提到了扩容死链和数据错乱的问题,并探讨了key的设计要求。对于对Java面试中的HashMap问题感兴趣的读者,本文将为您提供一些有用的技术和经验。 ... [详细]
  • 本文由编程笔记#小编为大家整理,主要介绍了源码分析--ConcurrentHashMap与HashTable(JDK1.8)相关的知识,希望对你有一定的参考价值。  Concu ... [详细]
  • 集合类中只能存放对象,而不能存放原始数据类型的元素,所以当有原始数据类型需要存放时,只能将其转换成相应的包装类对象。1)访问和遍历数组元素时,ArrayList的 ... [详细]
  • 一、HashMap1.HashMap概述:HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是 ... [详细]
  • 要讨论这些常用的默认初始容量和扩容的原因是:当底层实现涉及到扩容时,容器或重新分配一段更大的连续内存(如果是离散分配则不需要重新分配,离散分配都是插入新元素时动态分配内存),要将容器原来的数据全部复 ... [详细]
  • Iamtryingtomakeaclassthatwillreadatextfileofnamesintoanarray,thenreturnthatarra ... [详细]
  • Java容器中的compareto方法排序原理解析
    本文从源码解析Java容器中的compareto方法的排序原理,讲解了在使用数组存储数据时的限制以及存储效率的问题。同时提到了Redis的五大数据结构和list、set等知识点,回忆了作者大学时代的Java学习经历。文章以作者做的思维导图作为目录,展示了整个讲解过程。 ... [详细]
  • 本文介绍了如何在给定的有序字符序列中插入新字符,并保持序列的有序性。通过示例代码演示了插入过程,以及插入后的字符序列。 ... [详细]
  • 不同优化算法的比较分析及实验验证
    本文介绍了神经网络优化中常用的优化方法,包括学习率调整和梯度估计修正,并通过实验验证了不同优化算法的效果。实验结果表明,Adam算法在综合考虑学习率调整和梯度估计修正方面表现较好。该研究对于优化神经网络的训练过程具有指导意义。 ... [详细]
  • 动态规划算法的基本步骤及最长递增子序列问题详解
    本文详细介绍了动态规划算法的基本步骤,包括划分阶段、选择状态、决策和状态转移方程,并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中,在以后尽可能多地利用这些子问题的解,从而提高算法的效率。 ... [详细]
  • 本文详细介绍了Java中vector的使用方法和相关知识,包括vector类的功能、构造方法和使用注意事项。通过使用vector类,可以方便地实现动态数组的功能,并且可以随意插入不同类型的对象,进行查找、插入和删除操作。这篇文章对于需要频繁进行查找、插入和删除操作的情况下,使用vector类是一个很好的选择。 ... [详细]
  • 本文介绍了关于Java异常的八大常见问题,包括异常管理的最佳做法、在try块中定义的变量不能用于catch或finally的原因以及为什么Double.parseDouble(null)和Integer.parseInt(null)会抛出不同的异常。同时指出这些问题是由于不同的开发人员开发所导致的,不值得过多思考。 ... [详细]
author-avatar
回音爱Fred
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有