この問題では、単純にアイテムのリストと範囲を取り、すべてのアイテムを使用できる組み合わせを見つけようとしています。
例を次に示します。4 つの商品 (リンゴ、ナシ、モモ、オレンジ) があり、バスケットの最小 20%、最大 60% にそれぞれを含めるとします。たとえば、各アイテムの 25%、25%、25%、25%、または 30%、30%、20%、20% などを指定できますが、0%、0%、50%、50% は指定できません。指定された min% が 20% であるため、動作します。
プログラムは正常に動作しますが、リスト全体よりも少ないアイテムを使用します (すべてのソリューションで 4 つのアイテムではなく、一部のソリューションには 2 つまたは 3 つのアイテムが含まれていますが、これは私が望んでいるものではありません)。4 つのアイテムのリストを送信する場合、4 つのアイテムすべてを組み合わせて使用する組み合わせが必要です。私は大きなリストを使用する予定であり、サイズをすべてのみであり、最小％未満ではないアイテムにしたいので、これは望ましくありません。上記の情報を使用した例を次に示します (4 項目、20 ～ 60% の範囲):
good:
apples = 22
pears = 24
peach = 25
orange = 29
total: 100%
bad:
apples = 0
pears = 0
peach = 40
orange = 60
total: 100%
// Although total is correct, the example fails because
// the minimum of 20% per item was not obeyed.
なぜこれが起こっているのか本当に混乱していますが、賭けなければならない場合、再帰がリスト内のアイテムの数を取り、それを送り返す前に1を引く方法だと思います. メソッド内recursion_part：
private static void recursion_part(int k, int sum, int[] coeff) {
//k is number of items in the list(in this example its 4(0-3), sum is the remaining total percent to break down, coeff is the template to store values
//this recursively takes the sum and tries to find lower values of it until it equals zero using the bounds given
for (int c = low_bound[k]; c <= high_bound[k]; c++) {
coeff[k] = c;
int[] newcoeff = Arrays.copyOf(coeff, coeff.length);
if (c - sum == 0) {
results.add(newcoeff);
printresults(newcoeff);
break;
} else if (k > 0) {
recursion_part(k - 1, sum - c, newcoeff);
}
}
}
より大きなリストで作業したいのですが、気にしない結果がたくさん計算されると問題になると思います。リスト内のすべてのアイテムのみを処理し、範囲の制限内に留まるようにこれを再設計するにはどうすればよいですか?
リストにゼロがいくつあるかをチェックし、リストのサイズを下回った場合に中断するメソッドを配置することを考えましたが、空白の結果が得られるという事実は、その処理項目がリストよりも少ないことを意味し、リソースを無駄にしないようにプログラムを設計する方がよいと考えています。
コード全体は次のとおりです（説明どおりに機能しますが、前述のように結果はゼロです）：
import java.util.ArrayList;
import java.util.Arrays;
public class recursion_percent_returner {
static final int target_percent = 100;
static final String[] names = new String[] {"apples", "pears", "peach", "orange" };
static int[] low_bound = new int[names.length];
static int[] high_bound = new int[names.length];
static ArrayList results = new ArrayList(); //queue to store results
static int[] default_coeff = new int[names.length];
public static void main(String[] args) {
System.out.println("starting..");
System.out.println("list size " + names.length);
Arrays.fill(low_bound, 20); //fills the min list with default value
Arrays.fill(high_bound, 60); //fills the max list with default value
recursion_part(names.length-1,target_percent,default_coeff);
System.out.println("total size of results are " + results.size());
}
private static void recursion_part(int k, int sum, int[] coeff) {
//k is number of items in the list(in this example its 4(0-3), sum is the remaining total percent to break down, coeff is the template to store values
//this recursively takes the sum and tries to find lower values of it until it equals zero using the bounds given
for (int c = low_bound[k]; c <= high_bound[k]; c++) {
coeff[k] = c;
int[] newcoeff = Arrays.copyOf(coeff, coeff.length);
if (c - sum == 0) {
results.add(newcoeff);
printresults(newcoeff);
break;
} else if (k > 0) {
recursion_part(k - 1, sum - c, newcoeff);
}
}
}
private static void printresults(int[] newcoeff) {
for (int x = 0; x<newcoeff.length; x++) {
System.out.println(names[x] + " = " + newcoeff[x]);
}
System.out.println("*********");
}
}
私は、自分が求めている結果を達成するためのより良い方法に対してオープンです。
ps これは宿題ではなく、私は学生ではありません。奇妙な響きのプロキシの問題を見つける傾向があります。
編集
コード全体を含めましたが、ここにも出力があります。これは 2653 ソリューションのスニペットで、必要以上に生成されています。簡単に見ると、ほとんどが正しいことがわかりますが、下に行くにつれて、すべての値が使用されているわけではないことがわかります。すべての値を使用しているソリューションのみが必要です。0 値エントリがあってはなりません。