Knapsack problem
http://dbpedia.org/resource/Knapsack_problem an entity of type: Thing
El problema de la motxilla, altrament dit KP (en anglès, Knapsack Problem) és un problema d'. Modelitza una situació anàloga al fet d'omplir una motxilla, en la que no es pot posar més d'un cert pes, amb tot o una part d'un conjunt d'objectes. Aquests objectes tenen un pes i un valor determinat. Els objectes que es posen dins la motxilla han de maximitzar el valor total sense sobrepassar el pes màxim.
rdf:langString
Problém batohu je NP-úplný problém . Nechť je dáno n závaží, z nichž každé má jednoznačně určenou hmotnost. Některá z nich vybereme, a dáme je do uzavřeného batohu, který je neprůhledný (a který má sám nulovou hmotnost). Potom batoh zvážíme a určíme celkovou hmotnost, ze které se pokusíme určit, která závaží jsou uvnitř batohu.
rdf:langString
مسألة حقيبة الظهر هي مسألة تدخل في إطار الاستمثال التوافقي. فإذا كانت لدينا مجموعة من العناصر، لكل منها وزن و قيمة، فعليك أن تحدد العناصر التي تُدرج في الحقيبة، بحيث يكون مجموع أوزانها أقل من أو يساوي قدراً معيناً، وأن يكون مجموع القيم أعلى ما يكون.اسم هذه المسألة مأخوذ من حالة شخص ما لديه حقيبة ذات حجم محدد، وعليه أن يعبئها بالعناصر الأعلى قيمةً. تم تناول هذه المسألة منذ أكثر من قرن، وليس من المعروف كيف نشأ تعبير (مسألة حقيبة الظهر)، رغم أنه تم ذكرها في أعمال العالم الرياضي (1844-1956)، وهو من اقترح أن الاسم ربما قد يكون نشأ في التراث الشعبي قبل أن تتم نمذجة المسألة رياضياً.
rdf:langString
En algoritmia, el problema de la mochila, comúnmente abreviado por KP (del inglés Knapsack problem) es un problema de optimización combinatoria, es decir, que busca la mejor solución entre un conjunto finito de posibles soluciones a un problema. Modela una situación análoga al llenar una mochila, incapaz de soportar más de un peso determinado, con todo o parte de un conjunto de objetos, cada uno con un peso y valor específicos. Los objetos colocados en la mochila deben maximizar el valor total sin exceder el peso máximo.
rdf:langString
Il problema dello zaino, o in inglese Knapsack problem, è un problema di ottimizzazione combinatoria posto nel modo seguente. Sia dato uno zaino che possa sopportare un determinato peso e siano dati oggetti, ognuno dei quali caratterizzato da un peso e un valore. Il problema si propone di scegliere quali di questi oggetti mettere nello zaino per ottenere il maggiore valore senza eccedere il peso sostenibile dallo zaino stesso.
rdf:langString
ナップサック問題（ナップサックもんだい、Knapsack problem）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、n 種類の品物（各々、価値 vi、重量 wi）が与えられたとき、重量の合計が W を超えない範囲で品物のいくつかをナップサックに入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいか」という整数計画問題である。同じ種類の品物を1つまでしか入れられない場合（xi ∊ {0, 1}）や、同じ品物をいくつでも入れてよい場合（xi は0以上の整数）など、いくつかのバリエーションが存在する。 決定問題としてのナップサック問題は、「W, vi, wi のほかに価値の合計の目標 V が与えられたとき、重量の合計が W 以内でナップサック内の品物の価値の合計が V 以上になるような品物の選び方が存在するか」を判定することである。全ての品物について vi = wi である場合は、部分和問題と等価であるため、ナップサック問題は部分和問題の一般化である。ナップサック問題は、（部分和問題もそうであるが）NP困難と呼ばれる問題のクラスに属する。なお、部分和問題は同時にNP完全(NPかつNP困難)と呼ばれるクラスにも属する。 解法として、動的計画法を用いたや FPTAS の存在が知られており、実用的にはほぼ最適な解が得られる。
rdf:langString
배낭 문제(Knapsack Problem 냅색 프라블럼[*])는 조합 최적화의 유명한 문제이다. 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 이 배낭문제는 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0 이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem),짐을 쪼갤 수 없는 경우의 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라 부른다. 이 문제는 쪼갤 수 있는 경우에는 그리디 알고리즘으로 다항 시간에, 쪼갤 수 없는 경우에는 동적계획법(Dynamic Programming)등으로 에 풀 수 있다. 단, 쪼갤 수 없는 경우는 NP-완전이기 때문에 알려진 다항 시간 알고리즘은 없고, FPTAS만 존재한다. 배낭 문제에 대한 FPTAS는 와 김철언이 1975년에 개발하였다.
rdf:langString
Het knapzakprobleem is een NP-volledig probleem in de wiskunde, informatica en cryptografie. Het knapzakprobleem komt van het volgende vraagstuk: Gegeven een verzameling van objecten, elk met gewicht en waarde, bepaal welke (deel)verzameling van objecten meegenomen wordt in de knapzak, zodat het totale gewicht onder het maximum blijft en de totale waarde gemaximaliseerd wordt.
rdf:langString
Задача о рюкзаке (также задача о ранце) — NP-полная задача комбинаторной оптимизации. Своё название получила от конечной цели: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. С различными вариациями задачи о рюкзаке можно столкнуться в экономике, прикладной математике, криптографии и логистике. В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничение на суммарный вес.
rdf:langString
背包问题（英語：Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中，背包的空间有限，但我们需要最大化背包内所装物品的价值。背包问题通常出现在资源分配中，决策者必须分别从一组不可分割的项目或任务中进行选择，而这些项目又有时间或预算的限制。 背包问题历史悠久，甚至可以追溯到1897年。“背包问题”一词最早出现于数学家托拜厄斯·丹齐格的早期研究中，他研究的问题是如何打包行李，要求最大化所选行李的价值且不能超载。
rdf:langString
Das Rucksackproblem (auch englisch knapsack problem) ist ein Optimierungsproblem der Kombinatorik. Aus einer Menge von Objekten, die jeweils ein Gewicht und einen Nutzwert haben, soll eine Teilmenge ausgewählt werden, deren Gesamtgewicht eine vorgegebene Gewichtsschranke nicht überschreitet. Unter dieser Bedingung soll der Nutzwert der ausgewählten Objekte maximiert werden.
rdf:langString
The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem often arises in resource allocation where the decision-makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively.
rdf:langString
Bizkar-zorroaren buruketa konbinatoriala da. Pisu eta balio ezaguneko gauzakien multzo batean guztizko gehieneko balioko azpimultzoa aurkitzean datza, azpimultzoko gauzakien guztizko pisua muga batetik behera egotera murriztuta dagoen kasuan. Neurri mugatuko bizkar-zorro batean gauzakiak sartu behar diren kasuari aipamen eginez ematen zaio buruketari halako izena; bizkar-zorroan sartutako gauzakien balioen baturak gehienekoa izan behar du.
rdf:langString
En algorithmique, le problème du sac à dos, parfois noté (KP) (de l'anglais Knapsack Problem) est un problème d'optimisation combinatoire. Ce problème classique en informatique et en mathématiques modélise une situation analogue au remplissage d'un sac à dos. Il consiste à trouver la combinaison d'éléments la plus précieuse à inclure dans un sac à dos, étant donné un ensemble d'éléments de poids et de valeurs variables.
rdf:langString
Dyskretny problem plecakowy (ang. discrete knapsack problem) – jeden z najczęściej poruszanych problemów optymalizacyjnych. Nazwa zagadnienia pochodzi od maksymalizacyjnego problemu wyboru przedmiotów, tak by ich wartość sumaryczna była jak największa i jednocześnie mieściły się w plecaku. Przy podanym zbiorze elementów o podanej wadze i wartości należy wybrać taki podzbiór, by suma wartości była możliwie jak największa, a suma wag była nie większa od danej pojemności plecaka.
rdf:langString
O problema da mochila (em inglês, Knapsack problem) é um problema de optimização combinatória. O nome dá-se devido ao modelo de uma situação em que é necessário preencher uma mochila com objetos de diferentes pesos e valores. O objetivo é que se preencha a mochila com o maior valor possível, não ultrapassando o peso máximo. O problema da mochila é um dos 21 problemas NP-completos de Richard Karp, exposto em 1972. A formulação do problema é extremamente simples, porém sua solução é mais complexa. Este problema é a base do primeiro algoritmo de chave pública (chaves assimétricas).
rdf:langString
Kappsäcksproblemet är ett kombinatoriskt optimeringsproblem inom optimeringsläran. Namnet härstammar från den engelska beteckningen på problemet: knapsack problem. Ursprungligen beskrevs ett problem där saker med olika volym ska packas ner i en kappsäck med begränsat utrymme så att samtliga saker inte kan packas ner. Sakerna anses också ha olika värden för personen som ska ta med sig kappsäcken. Frågan är vilka saker som ska packas ned i kappsäcken så att värdet av de nedpackade sakerna blir som störst.
rdf:langString
Задача пакування рюкзака (англ. Knapsack problem) — задача комбінаторної оптимізації: для заданої множини предметів, кожен з яких має вагу і цінність, визначити яку кількість кожного з предметів слід взяти, так, щоб сумарна вага не перевищувала задану, а сумарна цінність була максимальною. Задача бере свою назву від доволі відомої ситуації, коли потрібно наповнити рюкзак, що здатен витримати деяку максимальну масу, предметами, кожен з яких має вартість (або корисність) та масу. Необхідно обрати об'єкти в такий спосіб, аби максимізувати сумарну вартість (або користь), але не перевищити максимально припустиму масу.
rdf:langString
rdf:langString
مسألة حقيبة الظهر
rdf:langString
Problema de la motxilla
rdf:langString
Problém batohu
rdf:langString
Rucksackproblem
rdf:langString
Problema de la mochila
rdf:langString
Bizkar-zorroaren buruketa
rdf:langString
Problème du sac à dos
rdf:langString
Problema dello zaino
rdf:langString
Knapsack problem
rdf:langString
배낭 문제
rdf:langString
ナップサック問題
rdf:langString
Knapzakprobleem
rdf:langString
Problem plecakowy
rdf:langString
Problema da mochila
rdf:langString
Задача о рюкзаке
rdf:langString
Kappsäcksproblemet
rdf:langString
Задача пакування рюкзака
rdf:langString
背包问题
xsd:integer
16974
xsd:integer
1123980612
xsd:date
2011-05-23
rdf:langString
El problema de la motxilla, altrament dit KP (en anglès, Knapsack Problem) és un problema d'. Modelitza una situació anàloga al fet d'omplir una motxilla, en la que no es pot posar més d'un cert pes, amb tot o una part d'un conjunt d'objectes. Aquests objectes tenen un pes i un valor determinat. Els objectes que es posen dins la motxilla han de maximitzar el valor total sense sobrepassar el pes màxim.
rdf:langString
Problém batohu je NP-úplný problém . Nechť je dáno n závaží, z nichž každé má jednoznačně určenou hmotnost. Některá z nich vybereme, a dáme je do uzavřeného batohu, který je neprůhledný (a který má sám nulovou hmotnost). Potom batoh zvážíme a určíme celkovou hmotnost, ze které se pokusíme určit, která závaží jsou uvnitř batohu.
rdf:langString
مسألة حقيبة الظهر هي مسألة تدخل في إطار الاستمثال التوافقي. فإذا كانت لدينا مجموعة من العناصر، لكل منها وزن و قيمة، فعليك أن تحدد العناصر التي تُدرج في الحقيبة، بحيث يكون مجموع أوزانها أقل من أو يساوي قدراً معيناً، وأن يكون مجموع القيم أعلى ما يكون.اسم هذه المسألة مأخوذ من حالة شخص ما لديه حقيبة ذات حجم محدد، وعليه أن يعبئها بالعناصر الأعلى قيمةً. تم تناول هذه المسألة منذ أكثر من قرن، وليس من المعروف كيف نشأ تعبير (مسألة حقيبة الظهر)، رغم أنه تم ذكرها في أعمال العالم الرياضي (1844-1956)، وهو من اقترح أن الاسم ربما قد يكون نشأ في التراث الشعبي قبل أن تتم نمذجة المسألة رياضياً.
rdf:langString
Das Rucksackproblem (auch englisch knapsack problem) ist ein Optimierungsproblem der Kombinatorik. Aus einer Menge von Objekten, die jeweils ein Gewicht und einen Nutzwert haben, soll eine Teilmenge ausgewählt werden, deren Gesamtgewicht eine vorgegebene Gewichtsschranke nicht überschreitet. Unter dieser Bedingung soll der Nutzwert der ausgewählten Objekte maximiert werden. Die Entscheidungsvariante des Rucksackproblems fragt, ob ein zusätzlich vorgegebener Nutzwert erreicht werden kann. Sie gehört zur Liste der 21 klassischen NP-vollständigen Probleme, von denen Richard Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte. In der Kryptographie wird häufig eine andere Entscheidungsvariante betrachtet. Dabei werden nur die Gewichte betrachtet und es wird gefragt, ob es eine Teilmenge der Objekte gibt, die einen vorgegebenen Gewichtswert genau erreicht. Diese Problemvariante wird auch als SUBSET-SUM bezeichnet. Basierend auf dieser Variante wurde das Public-Key-Kryptoverfahren Merkle-Hellman-Kryptosystem entwickelt, das sich allerdings als nicht besonders sicher herausstellte.
rdf:langString
En algoritmia, el problema de la mochila, comúnmente abreviado por KP (del inglés Knapsack problem) es un problema de optimización combinatoria, es decir, que busca la mejor solución entre un conjunto finito de posibles soluciones a un problema. Modela una situación análoga al llenar una mochila, incapaz de soportar más de un peso determinado, con todo o parte de un conjunto de objetos, cada uno con un peso y valor específicos. Los objetos colocados en la mochila deben maximizar el valor total sin exceder el peso máximo.
rdf:langString
Bizkar-zorroaren buruketa konbinatoriala da. Pisu eta balio ezaguneko gauzakien multzo batean guztizko gehieneko balioko azpimultzoa aurkitzean datza, azpimultzoko gauzakien guztizko pisua muga batetik behera egotera murriztuta dagoen kasuan. Neurri mugatuko bizkar-zorro batean gauzakiak sartu behar diren kasuari aipamen eginez ematen zaio buruketari halako izena; bizkar-zorroan sartutako gauzakien balioen baturak gehienekoa izan behar du. Aplikazio asko ditu, hala nola biosendagintzan, gaixoari eman beharreko sendagaiak aukeratzeko orduan, antibiotiko-zama mugatua denean. Igogailuak marraztean ere maiz ezartzen da, pisu jakin baterako zenbat pertsona eta nolakoak sar daitezkeen erabakitzeko.
rdf:langString
The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem often arises in resource allocation where the decision-makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively. The knapsack problem has been studied for more than a century, with early works dating as far back as 1897. The name "knapsack problem" dates back to the early works of the mathematician Tobias Dantzig (1884–1956), and refers to the commonplace problem of packing the most valuable or useful items without overloading the luggage.
rdf:langString
En algorithmique, le problème du sac à dos, parfois noté (KP) (de l'anglais Knapsack Problem) est un problème d'optimisation combinatoire. Ce problème classique en informatique et en mathématiques modélise une situation analogue au remplissage d'un sac à dos. Il consiste à trouver la combinaison d'éléments la plus précieuse à inclure dans un sac à dos, étant donné un ensemble d'éléments de poids et de valeurs variables. L'objectif du problème du sac à dos est de maximiser la valeur des objets pouvant être placés dans le sac à dos, sous la contrainte que le poids total des objets ne doit pas dépasser la capacité du sac à dos. Ce problème est considéré comme NP-difficile, ce qui signifie qu'il est difficile à résoudre, en particulier pour les grands ensembles d'items. Pour résoudre le problème du sac à dos, un certain nombre d'algorithmes et d'approches différents peuvent être utilisés, notamment la programmation dynamique, les algorithmes gourmands et la programmation en nombres entiers. Ces algorithmes peuvent être appliqués à un large éventail de problèmes réels, tels que préparer une valise pour un voyage, allouer des ressources dans une chaîne d'approvisionnement et optimiser la gestion des stocks.
rdf:langString
Il problema dello zaino, o in inglese Knapsack problem, è un problema di ottimizzazione combinatoria posto nel modo seguente. Sia dato uno zaino che possa sopportare un determinato peso e siano dati oggetti, ognuno dei quali caratterizzato da un peso e un valore. Il problema si propone di scegliere quali di questi oggetti mettere nello zaino per ottenere il maggiore valore senza eccedere il peso sostenibile dallo zaino stesso.
rdf:langString
ナップサック問題（ナップサックもんだい、Knapsack problem）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、n 種類の品物（各々、価値 vi、重量 wi）が与えられたとき、重量の合計が W を超えない範囲で品物のいくつかをナップサックに入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいか」という整数計画問題である。同じ種類の品物を1つまでしか入れられない場合（xi ∊ {0, 1}）や、同じ品物をいくつでも入れてよい場合（xi は0以上の整数）など、いくつかのバリエーションが存在する。 決定問題としてのナップサック問題は、「W, vi, wi のほかに価値の合計の目標 V が与えられたとき、重量の合計が W 以内でナップサック内の品物の価値の合計が V 以上になるような品物の選び方が存在するか」を判定することである。全ての品物について vi = wi である場合は、部分和問題と等価であるため、ナップサック問題は部分和問題の一般化である。ナップサック問題は、（部分和問題もそうであるが）NP困難と呼ばれる問題のクラスに属する。なお、部分和問題は同時にNP完全(NPかつNP困難)と呼ばれるクラスにも属する。 解法として、動的計画法を用いたや FPTAS の存在が知られており、実用的にはほぼ最適な解が得られる。
rdf:langString
배낭 문제(Knapsack Problem 냅색 프라블럼[*])는 조합 최적화의 유명한 문제이다. 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 이 배낭문제는 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0 이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem),짐을 쪼갤 수 없는 경우의 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라 부른다. 이 문제는 쪼갤 수 있는 경우에는 그리디 알고리즘으로 다항 시간에, 쪼갤 수 없는 경우에는 동적계획법(Dynamic Programming)등으로 에 풀 수 있다. 단, 쪼갤 수 없는 경우는 NP-완전이기 때문에 알려진 다항 시간 알고리즘은 없고, FPTAS만 존재한다. 배낭 문제에 대한 FPTAS는 와 김철언이 1975년에 개발하였다.
rdf:langString
Het knapzakprobleem is een NP-volledig probleem in de wiskunde, informatica en cryptografie. Het knapzakprobleem komt van het volgende vraagstuk: Gegeven een verzameling van objecten, elk met gewicht en waarde, bepaal welke (deel)verzameling van objecten meegenomen wordt in de knapzak, zodat het totale gewicht onder het maximum blijft en de totale waarde gemaximaliseerd wordt.
rdf:langString
Dyskretny problem plecakowy (ang. discrete knapsack problem) – jeden z najczęściej poruszanych problemów optymalizacyjnych. Nazwa zagadnienia pochodzi od maksymalizacyjnego problemu wyboru przedmiotów, tak by ich wartość sumaryczna była jak największa i jednocześnie mieściły się w plecaku. Przy podanym zbiorze elementów o podanej wadze i wartości należy wybrać taki podzbiór, by suma wartości była możliwie jak największa, a suma wag była nie większa od danej pojemności plecaka. Problem plecakowy często przedstawia się jako problem złodzieja rabującego sklep – znalazł on N towarów; j-ty przedmiot jest wart oraz waży Złodziej dąży do zabrania ze sobą jak najwartościowszego łupu, przy czym nie może zabrać więcej niż B kilogramów. Nie może też zabierać ułamkowej części przedmiotów (byłoby to możliwe w ciągłym problemie plecakowym). Podobny problem pojawia się często w kombinatoryce, teorii złożoności obliczeniowej, kryptografii oraz matematyce stosowanej. Decyzyjna wersja przedstawionego zagadnienia to pytanie: „Czy wartość co najmniej może być osiągnięta bez przekraczania wagi ?”.
rdf:langString
Задача о рюкзаке (также задача о ранце) — NP-полная задача комбинаторной оптимизации. Своё название получила от конечной цели: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. С различными вариациями задачи о рюкзаке можно столкнуться в экономике, прикладной математике, криптографии и логистике. В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничение на суммарный вес.
rdf:langString
Kappsäcksproblemet är ett kombinatoriskt optimeringsproblem inom optimeringsläran. Namnet härstammar från den engelska beteckningen på problemet: knapsack problem. Ursprungligen beskrevs ett problem där saker med olika volym ska packas ner i en kappsäck med begränsat utrymme så att samtliga saker inte kan packas ner. Sakerna anses också ha olika värden för personen som ska ta med sig kappsäcken. Frågan är vilka saker som ska packas ned i kappsäcken så att värdet av de nedpackade sakerna blir som störst. Kappsäcksproblemet existerar inte bara som det klassiska problemet som beskrivits ovan, utan kan även hittas vid bland annat schemaläggning av flygplansrutter och produktionsplanering.
rdf:langString
Задача пакування рюкзака (англ. Knapsack problem) — задача комбінаторної оптимізації: для заданої множини предметів, кожен з яких має вагу і цінність, визначити яку кількість кожного з предметів слід взяти, так, щоб сумарна вага не перевищувала задану, а сумарна цінність була максимальною. Задача бере свою назву від доволі відомої ситуації, коли потрібно наповнити рюкзак, що здатен витримати деяку максимальну масу, предметами, кожен з яких має вартість (або корисність) та масу. Необхідно обрати об'єкти в такий спосіб, аби максимізувати сумарну вартість (або користь), але не перевищити максимально припустиму масу. Задача часто виникає при , коли наявні фінансові обмеження, і вивчається в таких областях, як комбінаторика, інформатика, теорія складності, криптографія, прикладна математика. Описання задачі досить просте, але розв'язання — складне. Відомі алгоритми, на практиці, здатні розв'язати задачі досить великих розмірів. Однак, унікальне формулювання задачі, а також той факт, що вона присутня як підзадача у більших, загальніших проблемах, робить її важливою для наукових досліджень.
rdf:langString
O problema da mochila (em inglês, Knapsack problem) é um problema de optimização combinatória. O nome dá-se devido ao modelo de uma situação em que é necessário preencher uma mochila com objetos de diferentes pesos e valores. O objetivo é que se preencha a mochila com o maior valor possível, não ultrapassando o peso máximo. O problema da mochila é um dos 21 problemas NP-completos de Richard Karp, exposto em 1972. A formulação do problema é extremamente simples, porém sua solução é mais complexa. Este problema é a base do primeiro algoritmo de chave pública (chaves assimétricas). Normalmente este problema é resolvido com programação dinâmica, obtendo então a resolução exata do problema, mas também sendo possível usar PSE (procedimento de separação e evolução). Existem também outras técnicas, como usar algoritmo guloso, meta-heurística (algoritmos genéticos) para soluções aproximadas.
rdf:langString
背包问题（英語：Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中，背包的空间有限，但我们需要最大化背包内所装物品的价值。背包问题通常出现在资源分配中，决策者必须分别从一组不可分割的项目或任务中进行选择，而这些项目又有时间或预算的限制。 背包问题历史悠久，甚至可以追溯到1897年。“背包问题”一词最早出现于数学家托拜厄斯·丹齐格的早期研究中，他研究的问题是如何打包行李，要求最大化所选行李的价值且不能超载。
xsd:nonNegativeInteger
43641
