这个问题是在做这道习题时出现的:
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
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
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);
}
}
}
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);
}
}
}