しゅうすうアルゴリズム

今日yyは私に現実的な問題を提起した.
彼らの会社の財務は帳簿を合わせる必要があるので、数をそろえるツールを実現する必要があります.
具体的なニーズは、
財務総勘定サプライヤーにはいくつかの材料の単価があります.これらの材料の数を確定して、総価格が財務帳簿と一致するようにする必要があります.一部の材料には、数を超えてはいけないなどの制約があります.単価も計算されているので小数点以下4桁です.
アルゴリズムの実装には、多くの方法があるはずです.
その中で最も簡単なのは貧乏です.窮挙して組み合わせを並べる.自分の実現を窮めるのは難しくない.
これも主に貧乏なことを言っている.もっと良いアルゴリズムがあるはずです.
貧乏な欠点は遅いことだ.数はジオメトリ拡張です.材料の種類や個数に比例する.
計算総量はn 1*n 2*である.nn
以下のコードの実際の作業効率をテストし、jreの下で、1台の普通の開発機械が毎秒1000万個の組み合わせを検証することができます.速度は遅くない.jdk serverモードでは、差が少なく4倍速くなります.毎秒4000万本程度です.しかし、実際の応用の前では焼け石に水だ.7種類の材料があると仮定し、各拘束区間は0〜100であり、実際の組合せは約100の7次方、すなわち100兆である.この数級は、銀河でもしばらく走ると思います.

package com.allensoft.math;

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

import org.apache.commons.io.FileUtils;

public class CalNummber {
  
  private static final int MAX_NUM = 100;
  private static final int START_NUM = 1;
  
  private static long caltimes = 0l;
  
  private static Map<Integer,Integer> resultMap = new HashMap<Integer,Integer>();
  
  public static void main(String[] args) {
    
    //String filename = CalNummber.class.getClassLoader().getResource("/").getPath() + "number";
    String filename = "number";
    if(null != args && args.length > 0) {
      filename = args[0];
    } else {
      filename = CalNummber.class.getResource("/").getPath() + "number";
    }
    //System.out.println(CalNummber.class.getResource("").getPath() + "number");
    File paramFile = new File(filename);
    List<String> lineList = null;
    try {
      lineList = (List<String>)FileUtils.readLines(paramFile, "UTF-8");
    } catch (IOException e1) {
      // TODO Auto-generated catch block
      e1.printStackTrace();
    }
    
    List<Double> priceList = new ArrayList<Double>();
    List<Integer> lowerList = new ArrayList<Integer>();
    List<Integer> upperList = new ArrayList<Integer>();
    
    double result = 0d;
    
    if(null != lineList) {
      for(String line : lineList) {
        if(line.startsWith("result")) {
          String[] temp = line.split("=");
          result = Double.parseDouble(temp[1]);
        } else {
          String[] temp = line.split(",");
          if(temp.length == 3) {
            priceList.add(Double.valueOf(temp[0]));
            lowerList.add(Integer.valueOf(temp[1]));
            upperList.add(Integer.valueOf(temp[2]));
          } else {
            priceList.add(Double.valueOf(line));
            lowerList.add(Integer.valueOf(START_NUM));
            upperList.add(Integer.valueOf(MAX_NUM));
          }          
        }
      }
    }
    
    isCalable(priceList, lowerList, upperList, result);
    
    long current = System.currentTimeMillis();
    
    try{
      if(cal(0d,result,priceList,lowerList,upperList,0)) {
        
        System.out.println(caltimes);
        System.out.println("Cal take " + (System.currentTimeMillis() - current) + " ms");
        
        verify(resultMap,priceList,result);
      } else {
        
        System.out.println("no result found");
      }
    } catch(Exception e) {
      e.printStackTrace();
    }

  }
  
  private static boolean cal(Double startPrice, Double targetPrice, 
      List<Double> priceList, final List<Integer> lowerList, final List<Integer> upperList, int indexNum) {
    double currentPrice = 0; 
    for(int i = lowerList.get(indexNum); i <upperList.get(indexNum); i++) {
      caltimes++;
      if(caltimes%1000000000 == 0) {
        System.out.println(caltimes);
      }
      if(caltimes == Long.MAX_VALUE - 1) {
        caltimes = 0;
      }
      
      currentPrice = startPrice + i*priceList.get(indexNum);
      if(currentPrice == targetPrice) {
        System.out.println(indexNum + 1 + "---" + priceList.get(indexNum) + "---" + i);
        resultMap.put(indexNum, i);
        return true;
      }
      if(currentPrice > targetPrice) {
        if(indexNum == priceList.size() -1) {
          //System.out.println((indexNum + 1) + "---" + priceList.get(indexNum) + "---" + actualNumber);
          return false;
        } else {
          if(cal(startPrice, targetPrice, priceList,lowerList,upperList, indexNum + 1)){
            System.out.println((indexNum + 1) + "---" + priceList.get(indexNum) + "---" + (i-1));
            resultMap.put(indexNum, (i-1));
            return true;
          }
          continue;
        }
      } else {
        if(indexNum == priceList.size() -1) {
          continue;
        } else {
          if(cal(currentPrice, targetPrice, priceList, lowerList,upperList, indexNum + 1)){
            System.out.println((indexNum + 1) + "---" + priceList.get(indexNum) + "---" + i);
            resultMap.put(indexNum, i);
            return true;
          }
          continue;
        }
      }
    }
    return false;
  }
  
  private static void isCalable(List<Double> priceList, List<Integer> lowerList,final List<Integer> upperList, double targetValue) {
    System.out.println("If cal able ...");
    StringBuffer formular = new StringBuffer("Lower = 0");
    double calValue = 0d;
    for(int i=0; i<priceList.size(); i++) {
      formular.append("+" + lowerList.get(i) + "*" + priceList.get(i));
      calValue = calValue + lowerList.get(i)*priceList.get(i);
    }
    formular.append(" = " + calValue);
    formular.append(" < " + targetValue);
    
    System.out.println(formular);
    System.out.println("Verify result = " + Boolean.valueOf(calValue < targetValue));
    
    calValue = 0d;
    formular = new StringBuffer("Upper = 0");
    for(int i=0; i<priceList.size(); i++) {
      formular.append("+" + upperList.get(i) + "*" + priceList.get(i));
      calValue = calValue + upperList.get(i)*priceList.get(i);
    }
    formular.append(" = " + calValue);
    formular.append(" > " + targetValue);
    
    System.out.println(formular);
    
    System.out.println("Verify result = " + Boolean.valueOf(calValue > targetValue));
  }
  
  private static void verify(Map<Integer,Integer> resultMap, List<Double> priceList, double targetValue) {
    System.out.println("Verify ...");
    StringBuffer formular = new StringBuffer("0");
    double calValue = 0d;
    for(Entry<Integer,Integer> entry : resultMap.entrySet()) {
      formular.append("+" + entry.getValue() + "*" + priceList.get(entry.getKey()));
      calValue = calValue + entry.getValue()*priceList.get(entry.getKey());
    }
    formular.append(" = " + calValue);
    System.out.println(formular);
    System.out.println("Verify result = " + Boolean.valueOf(calValue == targetValue));
  }

}

貧乏挙で最適化する方法はありますか?実はあります.実際、実際の使用でもそうしています.
実際には、いくつかの計算結果が実際と大きくずれているか、小さすぎるか、大きすぎるかが見えます.
isCalableの方法は実はこの問題を表明したいということです.
上限の組合せ総価格と目標総価格の距離が近い場合、実際には、各材料の取材数が上限に近づき、以下の制限で計算する必要はないことを示している.逆に、下限が近いと、各材料の数が小さい可能性があります.従って、実際の材料数量取値区間は、上下限の総価格と、目標総価格の比を参照して最適化調整を行うことができ、実際に計算される数量が大幅に減少する.
窮挙法のほかに、もっと良い方法はありませんか.あるはずです.コードはまだ書いていません.しかし、一つの考え方を提供します.実は、これはa 1 x 1+a 2 x 2+...+に似ています.anxn=yのスレッド方程式を解く.方程式を初等変換してx 1の式を得ることができる.x 1を決定された値に等しくします.また初等変換をします.x 2の式が得られます.最後に,xnが非負の整数であれば結果は成立する.いずれにしても、x 1の値を新規からプッシュします.このように推す.このアルゴリズムの利点は盲目的な窮挙を避けることができることだ.効率はもっと高くなるはずです.