Задача о рюкзаке с использованием жадного метода. Пример 2. Метод 1 | Lec 49 | Разработка и анали...

Определение задачи о рюкзаке
Дан рюкзак вместимостью C/M, n предметов весом {w1, w2, w3,…….wn} и прибылью {p1, p2, p3,…….pn}. Цель состоит в том, чтобы выбрать подмножество из n предметов, которое поместится в рюкзак и максимизирует общую прибыль.

ЖАДНАЯ СТРАТЕГИЯ
Выбрать предмет с максимальной прибылью, помещающийся в рюкзак.
Выбрать предмет с минимальным весом, помещающийся в рюкзак.
Вычислить Pi/Wi и выбрать предмет с максимальным Pi/Wi.

Решение задачи о рюкзаке
Рассмотрим рюкзак вместимостью C или M.
Выбрать предметы из списка из n предметов весом Wi и прибылью Pi.
Получить решение, при котором
Сумма весов не должна превышать вместимость рюкзака C.
Оптимальный выбор — допустимый объект, обеспечивающий максимальную прибыль.
Оптимальное решение — допустимый объект, обеспечивающий максимальную прибыль.
Задачу можно сформулировать следующим образом:
Максимизировать ∑_(𝑖=1)^𝑛▒〖𝑃𝑖 𝑋𝑖〗
При условии ∑_(𝑖=1)^𝑛▒〖𝑊𝑖 𝑋𝑖〗 ≤ C или M
где 0 ≤ 𝑋𝑖 ≤ 1, 1 ≤ 𝑖 ≤ n
Прибыль и вес — положительные числа.

В этом видео объясняется пример реализации задачи о рюкзаке с использованием жадного алгоритма.
2. Найдите оптимальное решение для заданий с рюкзаком.
M = 15
n = 7
(p1, p2, p3, p4, p5, p6, p7) = (10, 5, 15, 7, 6, 18, 3)
(w1, w2, w3, w4, w5, w6, w7) = (2, 3, 5, 7, 1, 4. 1)

Ссылки
Задача о рюкзаке с использованием жадного метода. Введение
   • Knapsack Problem using Greedy Technique In...  

Задача о рюкзаке с использованием жадного метода. Пример 1. Метод 1
   • Knapsack Problem using Greedy Technique Ex...  

Задача о рюкзаке с использованием жадного метода. Пример 1. Метод 2
   • Knapsack Problem using Greedy Technique Ex...  

#knapsackproblem
#knapsackgreedytechnique
#greedymethod
#knapsackproblemusinggreedymethod
#knapsackexample
#greedytechnique
#cseguru
#shortestpathproblem
#csegurudaavideos
#cseguruadavideos
#singlesourceshortestpath
#designandanalysisofalgorithm
#ada
#daa

Видео о бинарном поиске:
Бинарный поиск:    • Binary Search General Method | Divide & Co...  
Пример метода бинарного поиска 1:    • Binary Search Technique Example1 | Divide ...  
Пример метода бинарного поиска 2:    • Binary Search Technique Example 2 | Divide...  
Временная сложность бинарного поиска:    • Time complexity of Binary Search | Divide ...  

Видео о быстрой сортировке
Этапы проектирования быстрой сортировки:    • Quick Sort General Method | Divide & Conqu...  
Пример быстрой сортировки 1:    • Quick Sort  Example1| Divide & Conquer Tec...  
Пример быстрой сортировки 2:    • Quick Sort  Example2 | Divide & Conquer Te...  
Алгоритм быстрой сортировки:    • Quick Sort  Algorithm | Divide & Conquer T...  

Видео о сортировке слиянием
Разделяй и властвуй:    • Divide and Conquer Technique | Master Theo...  
Метод сортировки слиянием:    • Merge Sort General Method | Divide & Conqu...  
Алгоритм сортировки слиянием:    • Merge Sort Algorithm | Divide & Conquer Te...  
Временная сложность сортировки слиянием:    • Time Complexity of Merge Sort | Divide & C...  

Пузырь Видео о сортировке
Рабочий пример пузырьковой сортировки | Полный перебор |:    • Bubble Sort working Example |  Brute Force...  
Алгоритм пузырьковой сортировки | Логическая трассировка с примером:    • Bubble Sort Algorithm Logic | Brute Force ...  

Сортировка выбором
Сортировка выбором | Пример алгоритма и анализ:    • Selection Sort Example & Analysis | Brute ...  

Видео CSEGuru
Видео о разработке компилятора #CSEGuru:
   • Compiler Design  

Видео CSEGuru о DAA
   • Design & Analysis of Algorithm  

Видео CSEGuru об операционных системах
   • Operating System  

CSEGuru Gate cse Видео
   • Gate cse  

Видео CSEGuru NET cse
   • NET cse  

Видео CSEGuru о структурах данных
   • Data Structure  

Видео CSEGuru об алгоритмах сортировки
   • Sorting Algorithm