2

我正在设计一个应用程序，其中我需要从一组肥料中选择最佳组合，即可以提供给定养分的最少肥料量。

例如，假设我需要提供 23g N（氮）和 23g P（磷），并且我有以下两组肥料：

第 1 组：
肥料 N P K (in g / 100 Kg)
A 23 23 0
B 18 46 0
C 46 0 0

第 2 组：
肥料 N P K (in g / 100 Kg)
D 23 23 0
E 18 46 0
F 16 0 0

在步骤 1 中：
我们可以选择 50 Kg 肥料 B 获得 23g P 并选择 ~30 Kg 肥料 C 以获得需要N。总共80公斤，而不是选择100公斤的肥料A。
在步骤2中：
我们最好选择100公斤的肥料D，而不是选择肥料E和肥料F。

现在，我正在尝试提出一种计算最佳组合的算法。我相信贪婪的方法是行不通的。因此，我尝试在 3D 矩阵上对 N、P、K 的所有可能整数值进行动态规划，但这会导致精度损失。而我只有有限的资源。
任何人都可以建议任何其他方法吗？
我觉得也许这可以建模为图形问题，但我不知道如何。


这是我编写的动态编程代码： 

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));

我正在失去精度，当我将它映射到数组索引时，我真的无能为力。

4

1 回答 1

3

这称为线性规划。你正在做线性优化。您可以使用单纯形算法来解决此类任务。

于 2013-06-21T10:35:10.937 回答