choose.java

找算法中一个经典问题：找最短哈米尔顿回路的算法实现。

public class choose {
    int size, count = 0;
    int maxvalue, maxtemp, maxtempweigh;
    int maxweigh;
    int valuetemp;
    int weightemp;
//    int weigh[];
//    int value[];
    int choos[], bestchos[];
    node[] data;

    public choose(node[] data_, int maxvalue_, int maxweigh_) {
//        weigh=weigh_;
//        value=value_;
        maxvalue = maxvalue_;
        maxweigh = maxweigh_;
        size = data_.length;
        choos = new int[size];
        bestchos = new int[size];
        valuetemp = weightemp = maxtemp = maxtempweigh = 0;
        data = data_;

    }

    public void switching(int begin) {
        if (begin > size - 1)
        {
            count++;
            System.out.print("the " + count + "th method:");
            for (int i = 0; i < size; i++)
                System.out.print(choos[i] + ",");
            System.out.println("weigh:" + weightemp + ",value:" + valuetemp);
            if (valuetemp > maxtemp) {
                maxtemp = valuetemp;
                maxtempweigh = weightemp;
                for (int i = 0; i < size; i++)
                    bestchos[i] = choos[i];
            }
        }
        else
        {
            if ((weightemp + data[begin].weigh) <= maxweigh) {
                choos[begin] = 1;
                weightemp += data[begin].weigh;
                valuetemp += data[begin].value;
                switching(begin + 1);

            }
           else return;
               choos[begin+1] = 0;
               weightemp -= data[begin].weigh;
               valuetemp -= data[begin].value;
               if (guolu(maxtemp, valuetemp, begin)) {
                   switching(begin + 2);
               }


        }
    }
        public boolean guolu(int maxtemp, int valuetemp, int k) {
            for (int i = k + 1; i < size; i++) {
                valuetemp += data[i].value;
            }
            if (valuetemp <= maxtemp)
                return false;
            else return true;
        }


}