| dbpprop:abstract
|
- The knapsack problem or rucksack 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 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 useful items. The problem often arises in resource allocation with financial constraints. A similar problem also appears in combinatorics, complexity theory, cryptography and applied mathematics. The decision problem form of the knapsack problem is the question "can a value of at least V be achieved without exceeding the weight W?"
- Das Rucksackproblem (oft mit RUCKSACK, KNAPSACK bezeichnet) 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.
- El problema de la motxilla, altrament dit KP (en anglès, Knapsack Problem) és un problema d'optimització combinatòria. 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.
- Problém batohu je NP-úplný problém kombinatorické optimalizace. 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.
- El tema que ocupa es solucionar el “problema de la mochila”, antes de ahondar en lo que recoge este concepto, sería conveniente ubicarlo en su ámbito de utilización. El problema de la mochila representa un problema de programación entera, estando ésta última dentro del campo de la Programación Matemática. Veamos qué se entiende por cada uno de estos conceptos:
- Le problème du sac à dos, aussi noté KP (en anglais, Knapsack Problem) est un problème d'optimisation combinatoire. Il modélise une situation analogue au remplissage d'un sac à dos, ne pouvant supporter plus d'un certain poids, avec tout ou partie d'un ensemble d'objets ayant chacun un poids et une valeur. Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum.
- Il Problema dello zaino, detto anche Knapsack problem, è un problema di ottimizzazione combinatoria posto nel modo seguente: sia dato uno zaino che possa supportare un determinato peso. Siano dati inoltre N oggetti, ognuno dei quali caratterizzato da un peso e un'utilità (ovvero un guadagno). Il problema si propone di scegliere quali di questi oggetti mettere nello zaino per ottenere la maggiore utilità senza eccedere nel peso sostenibile dallo zaino stesso.
- ファイル:Knapsack. svg ナップサック問題 ナップサック問題（-もんだい,Knapsack problem）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、「容量 C のナップサックが一つと、n 個の品物（各々、価値 pi, 容積 ci）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題である。同じ種類の品物を一つまでしか入れられない場合や、同じ品物をいくつでも入れてよい場合など、いくつかのバリエーションが存在する。 決定問題としてのナップサック問題は、「C, pi, ci のほかに価値の合計の目標 V が与えられたとき、容量 C 以内でナップサック内の品物の価値の合計が V 以上になるような品物の選び方はあるか」を判定することである。 全ての品物について pi = ci が成り立つとき、部分和問題と等価であるため、ナップサック問題は部分和問題を一般化したものといえる。ナップサック問題は、（部分和問題もそうだが）NP困難と呼ばれる問題のクラスに属する。なお、部分和問題は同時にNP完全と呼ばれるクラスにも属する。 動的計画法を用いた擬多項式時間アルゴリズムや FPTAS の存在が知られているため、実用的には、ほぼ最適解を得ることができる。
- Het knapzakprobleem is een NP-volledig probleem in de wiskunde, informatica en cryptografie. De naam van het probleem 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 de limiet blijft en de totale waarde gemaximaliseerd wordt.
- Dyskretny problem plecakowy (ang. binary knapsack problem) jest jednym z najczęściej poruszanych problemów optymalizacyjnych. Nazwa zagadnienia pochodzi od maksymalizacyjnego problemu wyboru przedmiotów, tak by ich sumaryczna wartość 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 <math>c_{j}</math> oraz waży <math>w_{j}</math>. 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 C może być osiągnięta bez przekraczania wagi W?"
- 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 para soluções aproximadas.
- Задача о ранце (рюкзаке) — одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов ограничен. Подобные задачи часто возникают в экономике, прикладной математике, криптографии. В общем виде, задачу можно сформулировать так: из неограниченного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.
- 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.
- Knapsack(sırt çantası) problemi en ünlü NP-Hard problemleri arasındadır. Pseudo-polynomial zamanda çözümünü sağlayan algoritmalar bulunmaktadır. Problemin karar problemi versiyonunun NP-Complete olduğu kanıtlanmıştır. Problemin polynomial zamanda çözümü ispatlanabilirse P=NP de ispatlanmış olacaktır. Problem tek kısıtlı bir maksimizasyon problemlemidir. Değişkenler sadece "0" veya "1" değerlerini alabilirler. Formülasyonu şu şekildedir: maximize <math>\sum_{j=1}^n p_j x_j. </math> Şu kısıtlara bağlı olarak <math>\sum_{j=1}^n w_j x_j \le c, \quad \quad x_j = 0\;\mbox{or}\;1, \quad j=1,\dots,n. </math>
- Задача пакування рюкзака — задача комбінаторної оптимізації. Задача полягає у наповнені рюкзака, що здатен витримати деяку максимальну вагу, предметами, кожен з яких має вартість (або корисність) та вагу. Необхідно обрати об'єкти в такий спосіб, аби максимізувати сумарну вартість (або користь), але не перевищити максимально припустиму вагу.
- 背包问题是一种组合优化的NP完全问题。它的名字来源于在给定一组物品时，如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。 0-1背包问题可以定义如下: maximize <math>\sum_{j=1}^n p_j x_j. </math> subject to <math>\sum_{j=1}^n w_j x_j \le c, \quad \quad x_j = 0\;\mbox{or}\;1, \quad j=1,\dots,n. </math> 推广的背包问题有二次背包问题，多维背包问题，多目标背包问题等。
|
| rdfs:comment
|
- The knapsack problem or rucksack 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 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 useful items.
- Das Rucksackproblem (oft mit RUCKSACK, KNAPSACK bezeichnet) 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.
- El problema de la motxilla, altrament dit KP (en anglès, Knapsack Problem) és un problema d'optimització combinatòria. 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.
- Problém batohu je NP-úplný problém kombinatorické optimalizace. 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.
- El tema que ocupa es solucionar el “problema de la mochila”, antes de ahondar en lo que recoge este concepto, sería conveniente ubicarlo en su ámbito de utilización. El problema de la mochila representa un problema de programación entera, estando ésta última dentro del campo de la Programación Matemática. Veamos qué se entiende por cada uno de estos conceptos:
- Le problème du sac à dos, aussi noté KP (en anglais, Knapsack Problem) est un problème d'optimisation combinatoire. Il modélise une situation analogue au remplissage d'un sac à dos, ne pouvant supporter plus d'un certain poids, avec tout ou partie d'un ensemble d'objets ayant chacun un poids et une valeur. Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum.
- Il Problema dello zaino, detto anche Knapsack problem, è un problema di ottimizzazione combinatoria posto nel modo seguente: sia dato uno zaino che possa supportare un determinato peso. Siano dati inoltre N oggetti, ognuno dei quali caratterizzato da un peso e un'utilità (ovvero un guadagno). Il problema si propone di scegliere quali di questi oggetti mettere nello zaino per ottenere la maggiore utilità senza eccedere nel peso sostenibile dallo zaino stesso.
- ファイル:Knapsack.
- Het knapzakprobleem is een NP-volledig probleem in de wiskunde, informatica en cryptografie. De naam van het probleem 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 de limiet blijft en de totale waarde gemaximaliseerd wordt.
- Dyskretny problem plecakowy (ang. binary knapsack problem) jest jednym z najczęściej poruszanych problemów optymalizacyjnych. Nazwa zagadnienia pochodzi od maksymalizacyjnego problemu wyboru przedmiotów, tak by ich sumaryczna wartość była jak największa i jednocześnie mieściły się w plecaku.
- 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.
- Задача о ранце (рюкзаке) — одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов ограничен.
- 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.
- Knapsack(sırt çantası) problemi en ünlü NP-Hard problemleri arasındadır. Pseudo-polynomial zamanda çözümünü sağlayan algoritmalar bulunmaktadır. Problemin karar problemi versiyonunun NP-Complete olduğu kanıtlanmıştır. Problemin polynomial zamanda çözümü ispatlanabilirse P=NP de ispatlanmış olacaktır. Problem tek kısıtlı bir maksimizasyon problemlemidir. Değişkenler sadece "0" veya "1" değerlerini alabilirler.
- Задача пакування рюкзака — задача комбінаторної оптимізації. Задача полягає у наповнені рюкзака, що здатен витримати деяку максимальну вагу, предметами, кожен з яких має вартість (або корисність) та вагу.
- 背包问题是一种组合优化的NP完全问题。它的名字来源于在给定一组物品时，如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。 0-1背包问题可以定义如下: maximize <math>\sum_{j=1}^n p_j x_j. </math> subject to <math>\sum_{j=1}^n w_j x_j \le c, \quad \quad x_j = 0\;\mbox{or}\;1, \quad j=1,\dots,n.
|
![[RDF Data]](/statics/sw-cube.png)
