私は、肥料のグループから、可能な限り最良の組み合わせ、つまり与えられた栄養素を供給することができる肥料の最小量を選択する必要がある用途を設計しています。
たとえば、23g の N (窒素) と 23g の P (リン) を供給する必要があり、次の 2 セットの肥料があるとします。
セット 1 :
肥料 N P K (g / 100 Kg)
A 23 23 0
B 18 46 0
C 46 0 0
セット 2 :
肥料 N P K (g / 100 Kg)
D 23 23 0
E 18 46 0
F 16 0 0
ステップ 1 :
50 Kg の肥料 B を選択して 23g P を取得し、～30 Kg の肥料 C を選択して、これは、100kg の肥料 A を選択する代わりに、合計 80kg になります。
ステップ 2
では、肥料 E と肥料 F を選択するよりも、100kg の肥料 D を選択する方がよいでしょう。
今、私は最適な組み合わせを計算するアルゴリズムを考え出そうとしています. 貪欲なアプローチはうまくいかないと思います。そこで、N、P、K のすべての可能な整数値に対して 3D マトリックスで動的計画法を試しましたが、精度が失われました。そして、私は限られたリソースしか持っていません。
誰でも同じ方法を提案できますか?
これはおそらくグラフの問題としてモデル化できると思いますが、その方法はわかりません。
私が書いた動的プログラミングのコードは次のとおりです。
void evaluateChoices() {
dp = new int[MAX + 1][MAX + 1][MAX + 1];
for(int i = 0; i < MAX; i++) {
for(int j = 0; j < MAX; j++) {
for(int k = 0; k < MAX; k++) {
if(i == 0 && j == 0 && k == 0) {
dp[0][0][0] = 0;
}
else {
considerCurrent(i, j, k);
}
}
}
}
}
void considerCurrent(int i, int j, int k) {
int minyet = Integer.MAX_VALUE;
for(int choice = 0; choice < numFertilizers; choice++) {
fertilizer fertilizerOption = fertilizerChoices[choice];
int amount;
if(fertilizerOption.N >= fertilizerOption.K && fertilizerOption.N >= fertilizerOption.P) {
amount = (100 / fertilizerOption.N) * i;
if(amount == 0) { // required amount is amount of N i.e i
continue;
}
if(((j - (fertilizerOption.P / 100)) * amount) >= 0 && ((k - (fertilizerOption.K / 100)) * amount) >= 0) {
int jIndex = (j - ((fertilizerOption.P / 100) * amount));
int kIndex = (k - ((fertilizerOption.K / 100) * amount));
if(dp[0][jIndex][kIndex] + amount < minyet) {
dp[i][j][k] = dp[0][jIndex][kIndex] + amount;
}
}
}
else if(fertilizerOption.P >= fertilizerOption.K && fertilizerOption.P >= fertilizerOption.N) {
amount = (100 / fertilizerOption.P) * j;
if(amount == 0) { // required amount is amount of P i.e j
continue;
}
if(((i - (fertilizerOption.N / 100)) * amount) >= 0 && ((k - (fertilizerOption.K / 100)) * amount) >= 0) {
int iIndex = (i - ((fertilizerOption.N / 100) * amount));
int kIndex = (k - ((fertilizerOption.K / 100) * amount));
if(dp[iIndex][0][kIndex] + amount < minyet) {
dp[i][j][k] = dp[iIndex][0][kIndex] + amount;
}
}
}
else {
amount = (100 / fertilizerOption.K) * k;
if(amount == 0) { // required amount is amount of K i.e k
continue;
}
if((i - ((fertilizerOption.N / 100) * amount)) >= 0 && (j - ((fertilizerOption.P / 100) * amount)) >= 0) {
int iIndex = ((i - (fertilizerOption.N / 100) * amount));
int jIndex = ((j - (fertilizerOption.P / 100) * amount));
if(dp[iIndex][jIndex][0] + amount < minyet) {
dp[i][j][k] = dp[iIndex][jIndex][0] + amount;
}
}
}
}
}
ここで、i、j、k は N、P、K の値です。
私が直面している問題は、次のようなインデックスを計算するときです。
int jIndex = (j - ((fertilizerOption.P / 100) * amount));
精度が低下しており、配列インデックスにマッピングしているため、実際には役に立ちません。