这个问题是在做这道习题时出现的:
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.txttotal ----总的商品个数
price[0]---id=0 的商品价格
price[1]---id=1 
.
.
price[total-1]文件policy.txttotal ----策略条数
maxRefer---每条策略最多涉及的商品种数
referNum id num[id] ... id num[id] totalPrice
--该条策略涉及的商品种数 id 需要购买id商品的个数... 总和价格(应当比单买便宜)示例文件数据如下:文件merchandise.txt
3
2
5
9文件policy.txt3
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

解决方案 »

  1.   

    注意一下好吗,我把程序还是写在回复里吧有问题的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.length;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<refer;i++){
    num[scanner.nextInt()]=scanner.nextInt();
    }
    }
    }
    void init(int totalKinds){
    refer=0;
    num=new int[totalKinds];
    for(int i=0;i<num.length;i++)
    num[i]=0;
    }
    public void printQuery(RandomAccessFile fileOut)throws Exception{
    fileOut.writeChar('(');
    for(int i=0;i<num.length;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.length;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<num.length;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<num.length;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<num.length;i++){
    s=s+num[i]+insert;
    }
    return s.hashCode();
    }*/
    }
    public class CommercialPromotion {
    float merchandise[];
    Policy policies[];
    int pNum;
    Hashtable<Query,Float> 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<t0;i++){
    merchandise[i]=mScanner.nextFloat();
    }
    t1=pScanner.nextInt();
    pNum=t1;//
    policies=new Policy[t0+t1];//
    pScanner.nextInt();
    for(i=0;i<t1;i++){
    k=pScanner.nextInt();
    policies[i]=new Policy(k);
    for(j=0;j<k;j++){
    policies[i].setNextInPair(pScanner.nextInt(),pScanner.nextInt());
    }
    policies[i].setTotalPrice(pScanner.nextFloat());
    }
    for(t1=t0+t1,j=0;i<t1;i++,j++){
    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<Query,Float>();
    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<policies[p].refer;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<merchandise.length;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<policies.length&&tmp.refer!=0;i++){//tmp.refer!=0 多余
    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<pn.length;i++) pn[i]=0;
    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<pNum&&q1.refer!=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<merchandise.length;i++,j++){
    if(q1.num[i]>0)
    pn[j]=q1.num[i];
    }
    boolean first=true;
    for(int i=0;i<pn.length;i++){
    if(pn[i]!=0){
    if(first){
    first=false;
    System.out.print(getCost(q)+" = ");
    }else
    System.out.print(" + ");
    if(i<pNum){
    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);
    }
    }
    }
      

  2.   

    没有问题的多维数组实现方式,其他实现与上面一摸一样: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.length;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<refer;i++){
    num[scanner.nextInt()]=scanner.nextInt();
    }
    }
    }
    void init(int totalKinds){
    refer=0;
    num=new int[totalKinds];
    for(int i=0;i<num.length;i++)
    num[i]=0;
    }
    public void printQuery(RandomAccessFile fileOut)throws Exception{
    fileOut.writeChar('(');
    for(int i=0;i<num.length;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.length;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<num.length;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<num.length;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<num.length;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<this.n;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<t0;i++){
    merchandise[i]=mScanner.nextFloat();
    }
    t1=pScanner.nextInt();
    pNum=t1;//
    policies=new Policy[t0+t1];//
    pScanner.nextInt();
    for(i=0;i<t1;i++){
    k=pScanner.nextInt();
    policies[i]=new Policy(k);
    for(j=0;j<k;j++){
    policies[i].setNextInPair(pScanner.nextInt(),pScanner.nextInt());
    }
    policies[i].setTotalPrice(pScanner.nextFloat());
    }
    for(t1=t0+t1,j=0;i<t1;i++,j++){
    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<policies[p].refer;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<merchandise.length;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<policies.length&&tmp.refer!=0;i++){//tmp.refer!=0 多余
    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<pn.length;i++) pn[i]=0;
    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<pNum&&q1.refer!=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<merchandise.length;i++,j++){
    if(q1.num[i]>0)
    pn[j]=q1.num[i];
    }
    boolean first=true;
    for(int i=0;i<pn.length;i++){
    if(pn[i]!=0){
    if(first){
    first=false;
    System.out.print(getCost(q)+" = ");
    }else
    System.out.print(" + ");
    if(i<pNum){
    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);
    }
    }
    }