Минимальный рюкзак не отображает правильные результаты

Question

Я хочу, чтобы рюкзак отображал лучшее решение, учитывая набор предметов, которые имеют определенный вес и стоимость, давайте предположим, что у него есть соответствующий array для хранения информации weight[] и cost[] Я хочурюкзак, который отображает стоимость предметов minimum для данного веса, он должен заполнять рюкзак или подходить к нему как можно ближе и отображать оптимальный результат.Код, который я написал, отображает правильное решение, только если рюкзак заполнен.Я просто хочу знать, что с ним не так с точки зрения алгоритма.

Я пытался модифицировать алгоритм ванильного ранца, чтобы получить minimum value, а не maximum.

public int MinimumCost(int weight[],int cost[], int n,int W){
    n = cost.length;
    int min_cost[][] = new int[n+1][W+1];

    for (int i = 0; i <= W; i++)
        min_cost[0][i] =999999;

    for (int i = 0; i <= n; i++)
        min_cost[i][0] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            if (weight[i-1] > j)
                min_cost[i][j] = min_cost[i-1][j];
            else
                min_cost[i][j] = Math.min(min_cost[i-1][j],min_cost[i-1][j-weight[i-1]]+cost[i-1]);

}


    return min_cost[n][W];
}

Я хочу, чтобы значение оптимального решения, МИНИМАЛЬНОЕ значение, заполняло (или подходило как можно ближе к заполнению) рюкзак заданного максимального веса.Спасибо!

Answer 1

Полагаю, что если вы не заполните полностью свой рюкзак, минимальное минимальное значение всегда будет равно 0 (без каких-либо предметов).

Таким образом, вы должны только рассмотреть вопрос о полном заполнении рюкзака; в противном случае либо минимум всегда равен 0, либо проблема не решена.

Если W - это максимальный вес, который вы можете рассмотреть, вы можете попытаться решить проблему нахождения минимальной перераспределения затрат при заполнении полностью рюкзака размером w с помощью * 1009. * w in 1 ... W .

Вам решать, какое решение среди 1 ... W является вашим любимым.