Задачата за раницата в Java

Проблем

Кои колети в кутията

Куриер кара товарен велосипед, а кутията му носи до 50 кг. В склада го чакат колети. Всеки има тегло и такса за доставка, а куриерът получава таксата за всеки доставен колет. Колет не се разделя: взима се цял или изобщо не се взима. Кои колети да вземе, за да изкара най-много?

Програмистът пробва всичко: за всеки колет „взимам“ или „не взимам“. Когато е решил за всички, проверява дали товарът се събира и колко носи. Колетите идват от склада. Тук ги строим с формула, за да са едни и същи на всеки език: тегло от 1 до 20 кг, такса от 2 до 40 €.

static long tries = 0;

static int tryAll(int[] weight, int[] fee, int cap, int i, int load, int sum) {
    if (i == weight.length) {
        tries++;
        return load <= cap ? sum : -1;
    }
    int skip = tryAll(weight, fee, cap, i + 1, load, sum);
    int take = tryAll(weight, fee, cap, i + 1, load + weight[i], sum + fee[i]);
    return Math.max(skip, take);
}

for (int n : new int[] {10, 20}) {
    int[] weight = new int[n];
    int[] fee = new int[n];
    for (int i = 0; i < n; i++) {
        weight[i] = 1 + i * 7 % 20;
        fee[i] = 2 + i * 11 % 39;
    }
    tries = 0;
    int best = tryAll(weight, fee, 50, 0, 0, 0);
    System.out.println(n + " колета: " + best + " €, " + tries + " комбинации");
}

10 колета: 169 €, 1024 комбинации
20 колета: 208 €, 1048576 комбинации

Всеки колет удвоява комбинациите: 10 колета са 1024, 20 са над милион. При 30 колета са над милиард, а при 50 колета са 1 125 899 906 842 624. С милиард комбинации в секунда това са около 13 дни, а куриерът тръгва в осем сутринта.

Идеята

Таблица колети × килограми

В рекурсията се повтарят едни и същи въпроси: „най-доброто от колет 7 нататък с 23 кг място“ идва по много различни пътища. Памет по двойката (колет, място) би спряла повторенията. Но и тук таблицата отдолу нагоре е по-проста и вече я знаеш. Само че тук подзадачата има две числа: колко колета гледаш и колко килограма място имаш. Таблицата е двумерна.

Четирите неща на таблицата:

Какво значи клетката. best[i][w] е най-голямата такса с първите i колета и товар до w кг.
Откъде идва. Колет i или не е вътре, и тогава е best[i − 1][w]. Или е вътре: таксата му плюс best[i − 1][w − теглото му], най-доброто без него за останалите килограми. Клетката пази по-голямото.
В какъв ред се пълни. Ред по ред: всеки ред чете само горния.
Къде е отговорът. Долу вдясно: всички колети, целият товар. Началото е редът 0, без колети: навсякъде 0.

Това е задачата за раницата (0/1 knapsack): неща с тегло и стойност, място с ограничение, и всяко нещо се взима цяло или не се взима. С нея се избират колети за курс, задачи за спринт с ограничени часове, реклами за ограничено ефирно време.

Виж го

Вземи или остави

Последният курс за деня: в кутията остават 6 кг място и чакат четири колета. Гледай двете клетки, които всяка клетка чете: горната („остави“) и стрелката от горния ред с таксата („вземи“):

static List<Integer> pack(int[] weight, int[] fee,
        int cap) {
    int n = weight.length;
    int[][] best = new int[n + 1][cap + 1];
    for (int i = 1; i <= n; i++) {
        int kg = weight[i - 1];
        int paid = fee[i - 1];
        for (int w = 0; w <= cap; w++) {
            best[i][w] = best[i - 1][w];
            if (kg <= w) {
                int take = best[i - 1][w - kg] + paid;
                best[i][w] = Math.max(best[i][w], take);
            }
        }
    }
    List<Integer> taken = new ArrayList<>();
    for (int i = n, w = cap; i > 0; i--) {
        if (best[i][w] != best[i - 1][w]) {
            taken.add(0, i);
            w -= weight[i - 1];
        }
    }
    return taken;
}

Стъпка по стъпка, с думи

pack(weight, fee, 6): best[i][w] е най-голямата такса с първите i колета и до w кг. Ред 0 е без колети, затова е само нули.
Остави колет i: най-доброто е каквото горният ред има за същите кг, best[i − 1][w]. Колет 1 тежи 4 кг, затова под 4 кг е само това.
Вземи колет i: таксата му плюс най-доброто на горния ред за останалите кг, best[i − 1][w − kg]. При 4 кг: 10 € + 0 = 10 € бие 0.
Ред 3, 6 кг: колет 3 (3 кг, 6 €) плюс най-доброто за 3 кг без него, 7 €: 13 € > 10 €. Два по-евтини колета бият най-скъпия на килограм.
Назад от долния десен ъгъл: същото като горе значи, че колетът е оставен, различно значи взет. Колет 4 не е взет, колет 3 е взет, колет 2 е взет, колет 1 не е взет: 2 + 3 = 13 €.

int[] weight = {4, 3, 3, 1};
int[] fee = {10, 7, 6, 2};
System.out.println(pack(weight, fee, 6));

[2, 3]

Идеята

Кои колети

Таблицата казва колко, а куриерът трябва да знае кои. Отговорът е в самата таблица. Тръгваш от долния десен ъгъл. Ако клетката е същата като горната, колет i не е нужен за нея: качваш се ред нагоре. Ако е различна, колет i е взет: качваш се ред нагоре и вървиш наляво с теглото му. Така до ред 0.

Днешните 20 колета и кутия от 50 кг:

static int paid(int[] fee, List<Integer> taken) {
    int sum = 0;
    for (int p : taken) {
        sum += fee[p - 1];
    }
    return sum;
}

int[] weight = new int[20];
int[] fee = new int[20];
for (int i = 0; i < 20; i++) {
    weight[i] = 1 + i * 7 % 20;
    fee[i] = 2 + i * 11 % 39;
}
List<Integer> taken = pack(weight, fee, 50);
String list = taken.stream().map(String::valueOf).collect(Collectors.joining(" + "));
System.out.println(list + ": " + paid(fee, taken) + " €");

1 + 4 + 7 + 8 + 10 + 11 + 13 + 14: 208 €

Колетите тежат 48 кг и носят 208 €, най-много от всички над милион комбинации. Таблицата има 20 реда с колети по 51 клетки, общо 1020 клетки.

Пробвай

Попълни

Колет i влиза. Колко килограма остават за другите колети?

static List<Integer> pack(int[] weight, int[] fee,
        int cap) {
    int n = weight.length;
    int[][] best = new int[n + 1][cap + 1];
    for (int i = 1; i <= n; i++) {
        int kg = weight[i - 1];
        int paid = fee[i - 1];
        for (int w = 0; w <= cap; w++) {
            best[i][w] = best[i - 1][w];
            if (kg <= w) {
                int take = best[i - 1][] + paid;
                best[i][w] = Math.max(best[i][w], take);
            }
        }
    }
    List<Integer> taken = new ArrayList<>();
    for (int i = n, w = cap; i > 0; i--) {
        if (best[i][w] != best[i - 1][w]) {
            taken.add(0, i);
            w -= weight[i - 1];
        }
    }
    return taken;
}

Идеята

Защо не най-скъпото на килограм

Изглежда разумно: смяташ таксата на килограм за всеки колет и взимаш най-скъпия, който се събира, после следващия. В курса от 6 кг колет 1 е 2,50 € на килограм, колет 2 е около 2,33, колет 3 е 2, колет 4 е 2.

static List<Integer> greedy(int[] weight, int[] fee, int cap) {
    boolean[] used = new boolean[weight.length];
    List<Integer> taken = new ArrayList<>();
    while (true) {
        int pick = -1;
        double rate = 0;
        for (int i = 0; i < weight.length; i++) {
            double perKg = (double) fee[i] / weight[i];
            if (!used[i] && weight[i] <= cap && perKg > rate) {
                pick = i;
                rate = perKg;
            }
        }
        if (pick < 0) {
            return taken;
        }
        used[pick] = true;
        taken.add(pick + 1);
        cap -= weight[pick];
    }
}

int[] weight = {4, 3, 3, 1};
int[] fee = {10, 7, 6, 2};
List<Integer> fast = greedy(weight, fee, 6);
List<Integer> best = pack(weight, fee, 6);
String a = fast.stream().map(String::valueOf).collect(Collectors.joining(" + "));
String b = best.stream().map(String::valueOf).collect(Collectors.joining(" + "));
System.out.println("по €/кг: " + a + " = " + paid(fee, fast) + " €");
System.out.println("таблица: " + b + " = " + paid(fee, best) + " €");

по €/кг: 1 + 4 = 12 €
таблица: 2 + 3 = 13 €

Колет 1 влиза пръв и заема 4 кг. Остават 2 кг, и в тях влиза само колет 4. Колети 2 и 3 щяха да напълнят 6-те кг докрай и да носят повече. Правилото избира без да погледне назад, а първият му избор затваря по-добрата комбинация. Таблицата пробва и двете възможности за всеки колет и всяко място.

Ако колетите можеха да се режат (пясък, гориво), най-скъпото на килограм първо щеше да е вярно. Кога такова правило работи и кога лъже, е урокът „Кога алчният алгоритъм греши“.

Идеята

Един ред вместо таблица

Всеки ред чете само горния. Значи не трябва цялата таблица: стига един ред best[0..W], презаписван колет след колет. Когато само сумата е нужна, програмата става по-къса:

static int bestFee(int[] weight, int[] fee, int cap) {
    int[] best = new int[cap + 1];
    for (int i = 0; i < weight.length; i++) {
        for (int w = cap; w >= weight[i]; w--) {
            int take = best[w - weight[i]] + fee[i];
            best[w] = Math.max(best[w], take);
        }
    }
    return best[cap];
}

int[] weight = {4, 3, 3, 1};
int[] fee = {10, 7, 6, 2};
System.out.println(bestFee(weight, fee, 6) + " €");

13 €

Важното е посоката: килограмите вървят отгоре надолу, от W към теглото на колета. Клетката w чете best[w − теглото], която е вляво от нея. Отгоре надолу тази клетка още не е презаписана в този кръг, значи е от горния ред, без текущия колет. Така колетът влиза най-много веднъж.

Пробвай

Предвиди изхода

5 кг място и три колета: 2 кг за 3 €, 3 кг за 4 €, 4 кг за 5 €. Колко отпечатва програмата?

static int bestFee(int[] weight, int[] fee, int cap) {
    int[] best = new int[cap + 1];
    for (int i = 0; i < weight.length; i++) {
        for (int w = cap; w >= weight[i]; w--) {
            int take = best[w - weight[i]] + fee[i];
            best[w] = Math.max(best[w], take);
        }
    }
    return best[cap];
}

int[] weight = {2, 3, 4};
int[] fee = {3, 4, 5};
System.out.println(bestFee(weight, fee, 5) + " €");

Отговор

8 €

7 €

5 €

Пробвай

Намери грешката

Колега обърнал посоката на килограмите. За курса от 6 кг програмата му казва:

int[] weight = {4, 3, 3, 1};
int[] fee = {10, 7, 6, 2};
System.out.println(bestFee(weight, fee, 6) + " €");

14 €

А най-доброто е 13 €. На кой ред е грешката?

Избери реда с грешката.

Виж го

Измери го: всички комбинации срещу таблицата

Броим проверените комбинации и сравненията „вземи или остави“ в реда. Кутията е 50 кг. Над 20 колета комбинациите не се пускат: те са точно 2ⁿ, затова оценката с „≈“ е точна.

Всички комбинации O(2ⁿ)
Таблица (до 50 кг) O(n)

Алгоритъм	n = 10	n = 20	n = 30	n = 40
Всички комбинации	1024	1 048 576	≈ 1 073 741 824	≈ 1 099 511 627 776
Таблица (до 50 кг)	425	810	1235	1620

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

static int bestFee(int[] weight, int[] fee, int cap) {
    int[] best = new int[cap + 1];
    for (int i = 0; i < weight.length; i++) {
        for (int w = cap; w >= weight[i]; w--) {
            int take = best[w - weight[i]] + fee[i];
            best[w] = Math.max(best[w], take);
        }
    }
    return best[cap];
}

Всеки нов колет удвоява комбинациите, а на таблицата добавя един ред: най-много 50 сравнения. При 40 колета таблицата прави 1620 сравнения, а комбинациите са над трилион. Затова и таблицата расте права: с постоянни 50 кг тя е O(n). Цената на W е в „По-точно“ долу.

По-точно, за любопитните

Същите числа на твоя език:

static long tries = 0;

static int tryAll(int[] weight, int[] fee, int cap, int i, int load, int sum) {
    if (i == weight.length) {
        tries++;
        return load <= cap ? sum : -1;
    }
    int skip = tryAll(weight, fee, cap, i + 1, load, sum);
    int take = tryAll(weight, fee, cap, i + 1, load + weight[i], sum + fee[i]);
    return Math.max(skip, take);
}

static int bestFee(int[] weight, int[] fee, int cap) {
    int[] best = new int[cap + 1];
    for (int i = 0; i < weight.length; i++) {
        for (int w = cap; w >= weight[i]; w--) {
            tries++;
            int take = best[w - weight[i]] + fee[i];
            best[w] = Math.max(best[w], take);
        }
    }
    return best[cap];
}

for (int n : new int[] {10, 20}) {
    int[] weight = new int[n];
    int[] fee = new int[n];
    for (int i = 0; i < n; i++) {
        weight[i] = 1 + i * 7 % 20;
        fee[i] = 2 + i * 11 % 39;
    }
    tries = 0;
    tryAll(weight, fee, 50, 0, 0, 0);
    long all = tries;
    tries = 0;
    bestFee(weight, fee, 50);
    System.out.println(n + " колета: комбинации " + all + ", таблица " + tries);
}

10 колета: комбинации 1024, таблица 425
20 колета: комбинации 1048576, таблица 810

Упражнение

Курсът от входа

Реши задачата в редактора си.

Курс. Прочети товара в кг на първия ред, теглата на колетите на втория и таксите на третия. Отпечатай кои колети да вземе куриерът и колко изкарва. Ползвай pack и paid от урока.

15
5 6 3 4 7 2
11 14 6 9 15 3

1 + 2 + 4: 34 €

Още задачи

И колко кг. Отпечатай и колко тежат взетите колети, и колко място остава.
Спешни колети. Колет 2 трябва да тръгне непременно. Как ще го вкараш в задачата, без да пишеш нова таблица? (Подсказка: махни го от списъка и намали товара с теглото му.)
Две кутии. Велосипедът има две кутии по 25 кг. Защо не стига да решиш задачата за 50 кг?

По-точно

По-точно: цената на W

Защо „O(n · W)“ не значи „бързо винаги“.

По-точно, за любопитните

Псевдополиномиално време. Таблицата има n · W клетки. n е колко колета има, но W е стойността на капацитета, а не колко неща има във входа. Ако теглата са в грамове, кутията от 50 кг става W = 50 000 и таблицата е хиляда пъти по-голяма. Ако капацитетът е милиард (байтове на диск, центове на бюджет), таблицата не се събира в паметта, а броят на колетите е същият. Време, което е полином в n и в стойността на W, но не в дължината на W в цифри, се нарича псевдополиномиално. Всяка цифра повече в W умножава работата по 10. Затова при огромни W и малко колети пробването на комбинации с добро рязане понякога е по-бързо.

Памет. Цялата таблица е (n + 1) · (W + 1) числа, един ред е W + 1. Но редът сам не казва кои колети: за връщането назад трябват всички редове, или поне по един бит „взет“ за всяка клетка.

Когато колетите са неограничени. Ако от всеки вид има колкото искаш (кашони с вода по 6 кг, всеки за 4 €), отгоре надолу вече е грешно, а отдолу нагоре е точно това, което трябва: всеки вид може да влезе пак. Това е същият цикъл като в рестото, където всяка монета може да се ползва много пъти. Грешката от „Намери грешката“ е вярното решение на друга задача.

Тест

Провери се

1. Какво значи клетката best[i][w] в таблицата на раницата?Таксата на колет i, ако тежи w кгКолко колета от първите i се събират в w кгНай-голямата такса, която се взима само от първите i колета, с товар до w кг

2. Клетката best[i][w] избира между две неща. Кои?Без колет i: best[i − 1][w]. С колет i: таксата му плюс best[i − 1][w − теглото му]Най-тежкият или най-скъпият колетКолет i или колет i − 1

3. Колетите са 4 кг за 10 €, 3 кг за 7 €, 3 кг за 6 € и 1 кг за 2 €, а мястото е 6 кг. Какво взима правилото „най-скъпото на килограм, което още се събира“?Колети 1 и 4, 12 €, а най-доброто е колети 2 и 3, 13 €Колети 2 и 3, 13 €, най-добротоСамо колет 1, 10 €

4. В таблицата с един ред капацитетът върви отгоре надолу. Какво става, ако върви отдолу нагоре?Нищо, отговорът е същиятПрограмата чете извън масиваbest[w − теглото] вече може да съдържа същия колет, и той влиза два пъти

5. Таблицата е O(n · W). Защо това не е „бързо винаги“?Защото n · W винаги е повече от 2ⁿЗащото таблицата се пълни два пътиW е числото на капацитета, а не броят на нещата. С грамове вместо килограми таблицата става хиляда пъти по-голяма

Задачата за раницата

Бисквитки