Как решить проблему ранца с минимизацией стоимости? - PullRequest
Новая
       33

Как решить проблему ранца с минимизацией стоимости?

1 голос
/ 03 апреля 2019

Мне дают файл с информацией о калориях и жирности в этой форме ->

330 350 100 230 // Это калории 30 27 10 10 // Это жир

Пользователь также может ввести количество «требуемых калорий».

Моя задача - использовать динамическое программирование, чтобы создать алгоритм, который выводит количество калорий и список блюд, используемых для его достижения.Каждую еду можно использовать только один раз, жир должен быть минимизирован, и мой выход калорий должен быть как можно ближе к количеству «требуемых калорий», которое я получил в качестве входных данных ...

Я рассчитывалчто это очень похоже на проблему с рюкзаком: мои «требуемые калории» - это объем моей сумки, калории - это вес каждого предмета, а жир - ценность каждого предмета.

Проблема, насколько я могу судить, состоит в том, что в отличие от обычной проблемы с ранцем, когда значение должно быть максимизировано, в этом случае оно должно быть минимизировано.

private intimumFat (int wantedCalories, int [] calories, int [] fat) {

    int n = fat.length;

    int min_fat[][] = new int[n+1][wantedCalories+1];

    // Fill 0th Row with infinity
    for (int i=0; i <= wantedCalories; i++) {
        min_fat[0][i] = Integer.MAX_VALUE;
    }

    // Fill 0th Column with 0
    for (int i=1; i<=n; i++) {
        min_fat[i][0] = 0;
    }

    // Check each weight one by one
    for (int i=1; i<=n; i++) {
        System.out.println(i + ")");
        for (int j=1; j<=wantedCalories; j++) {
            if (calories[i-1] > j) {
                min_fat[i][j] = min_fat[i-1][j];
            } else {
                min_fat[i][j] = Math.min(min_fat[i-1][j], min_fat[i][j-calories[i-1]] + fat[i-1]);
            }
            System.out.print(min_fat[i-1][j-1] + " ");
        }
    }

    return min_fat[n][wantedCalories];
}

При выполнении приведенного выше кода мои результаты отрицательные, что, насколько я могу судить, происходитпотому что Integer.MAX_VALUE переполняется.Я не уверен, как мне продолжить, потому что независимо от того, что я положил в Math.min, он всегда будет отдавать предпочтение min_fat [i-1] [j].Я ожидал, что результатом будет количество жира, использованное планом питания, чтобы я мог затем проследить и найти общее количество использованных калорий, а также продукты, которые составляли план питания, но это явно не то, что произошло.

...