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

Question

有问题的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);
}
}
}请继续看Hashtable的已在元素无法找到的问题2

Answer 1

没有问题的多维数组实现方式，其他实现与上面一摸一样：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);
}
}
}