私の目標は、プログラムにいくつかの項目 (文字列)、範囲、および目標パーセントを与え、各項目の可能なすべてのパーセントを与えることです。たとえば、食料品店に行ってリンゴとナシのバスケットを持っていて、すべてのアイテムを使用して得られるすべてのパーセンテージを知りたいと想像してください (完全な解決策ではありません。私はこれを手作業で行っています)。
{Apple:50, Pears:50}, {Apple:75, Pears:25}, {Apple:90, Pears:10},etc.
20〜50の範囲で同じことを行うと（単一のアイテムが持つことができる最大値は50％で、最小値は20％であることを意味します）、唯一の結果は次のとおりです：（
{Apple:50, Pears:50}アイテムは2つしかなく、50を超えることはできないため） ％ 重さ）
アイテムに関連付けられた値/重みがないため、いくつかの大きな違いがあるナップザックの問題と同様の特性があると思いました（ただし、アイテムをナップザックに収めようとするナップザックの問題のように、target_percent、100 内に値を収めようとしています） %)。また、問題を分解する方法がわからないため、一般的な動的プログラミングのアイデアを適用するのにも問題があります(典型的なナップザックの問題は結果を構築し、結果を「キャッシュ」して再利用しますが、Xのリストがある場合アイテム、範囲内で使用するすべての X アイテムが必要です)。
私は力ずくでこれを行うことができますが、すべてを試すだけなので、効率的であるとは感じませんPear が 25% を超える必要がある理由はありません..境界はリスト、範囲、および target_percent のサイズです..5 ～ 20 の範囲の 20 ～ 30 個のリスト項目、または 1 ～ 5 の範囲の 50 個の項目がある可能性があります。問題の解決方法を理解したら設定できるので、target_percent の部分は質問に示していませんが、基本的にはすべて例では最大 100% を想定していますが、バスケットにすでに 20% のオレンジがあり、リンゴ/ナシを使用して残りの 80% を埋める方法を確認することもできます)。
私の質問は、これにどのようにアプローチできますか（使用するアイデアロジック、例、またはルックアップできるプロキシ問題）? 動的プログラミングはこの問題に適していますか、それともこれをより小さなチャックに分割できないという事実が問題なのですか (常にリスト内のすべての項目が含まれているため、構築されていないことを思い出してください)? 誰かが私を正しい方向に向けることができれば、役立つかもしれないトピックを喜んで研究します (これを理解するために 2 日間費やした後、動的プログラミングのルートが正しいかどうかはわかりません)。また、このタイプの問題の名前はありますか?
これが私の（壊れた）ブルートフォースアプローチです（実際には期待どおりに機能していませんが、ブルートフォースメソッドのアイデアが得られるかもしれません）：
import java.util.ArrayList;
import java.util.Arrays;
public class brute_force_percent_returner {
static String[] data = new String[]{"Apple", "Pears"};
static int[] coeff = new int[data.length];
static ArrayList<int[]> queue = new ArrayList<int[]>();
public static void main(String[] args) {
System.out.println("Starting");
recursion(0,data);
for (int[] item : queue) {
for (int item2 = 0; item2<data.length; item2++) {
System.out.print(data[item2] + " = " + item[item2] + " ");
}
System.out.println();
}
}
private static void recursion(int k, String[] data2) {
// this is not exactly working
for (String item: data2) {
for (int x = 0; x<5;x++) {
int[] coeff_temp = Arrays.copyOf(coeff, coeff.length);
coeff_temp[k] = x;
queue.add(coeff_temp);
}
}
if (k == data.length-1) {
return;
} else {
recursion(k+1, data2);
}
}
}
それが役立つ場合、私が作成しようとしていたソリューションは、これに多少基づいていました(ナップザックの問題ですが、多数の変数に対して非常に高速であるように見えますが、このケアでは、その処理はリスト内のアイテムですが、私の場合はリストは単なる文字列です):
public class TurboAdder {
private static final int[] data = new int[] { 5, 10, 20, 25, 40, 50 };
private static class Node {
public final int index;
public final int count;
public final Node prevInList;
public final int prevSum;
public Node(int index, int count, Node prevInList, int prevSum) {
this.index = index;
this.count = count;
this.prevInList = prevInList;
this.prevSum = prevSum;
}
}
private static int target = 100;
private static Node sums[] = new Node[target+1];
// Only for use by printString.
private static boolean forbiddenValues[] = new boolean[data.length];
public static void printString(String prev, Node n) {
if (n == null) {
System.out.println(prev);
} else {
while (n != null) {
int idx = n.index;
// We prevent recursion on a value already seen.
if (!forbiddenValues[idx]) {
forbiddenValues[idx] = true;
printString((prev == null ? "" : (prev+" + "))+data[idx]+"*"+n.count, sums[n.prevSum]);
forbiddenValues[idx] = false;
}
n = n.prevInList;
}
}
}
public static void main(String[] args) {
for (int i = 0; i < data.length; i++) {
int value = data[i];
for (int count = 1, sum = value; count <= 100 && sum <= target; count++, sum += value) {
for (int newsum = sum+1; newsum <= target; newsum++) {
if (sums[newsum - sum] != null) {
sums[newsum] = new Node(i, count, sums[newsum], newsum - sum);
}
}
}
for (int count = 1, sum = value; count <= 100 && sum <= target; count++, sum += value) {
sums[sum] = new Node(i, count, sums[sum], 0);
}
}
printString(null, sums[target]);
}
}