Résolvez efficacement le problème de KNAPACACK 0-1 non pondé

Question

J'ai $ n $ éléments et une corbeille de taille $ B $ unités. Chaque élément $ j $ consomme $ w_j $ unités de $ B $ lorsqu'il est placé dans le sac à dos. L'article apparaît un par un de manière en ligne. Une fois l'article $ I $ apparaît, nous devons le placer dans la corbeille (irrévocablement) ou l'ignorer. L'objectif est d'optimiser le nombre d'éléments placés dans la corbeille. (Toutes les entrées sont des entiers positifs.)

L'algorithme hors ligne est facile: placez les éléments dans la commande $ w_1 \ leq w_2 \ leq \ cdots \ leq w_n $ jusqu'à ce que la corbeille soit pleine.

Comment puis-je résoudre ce problème de manière en ligne? Mon approche consiste à randomiser les choix: une fois l'élément $ j $ apparaît, placez-le dans la corbeille avec probabilité $ p_j $ < / Span> et l'ignorer autrement.

Answer 1

Eh bien que vous avez déjà remarqué, ou du moins non mentionné, il est facile de voir qu'il n'y a pas d'algorithme compétitif déterministe pour votre problème.(Contreexamples n'a besoin que de deux éléments et vous pouvez utiliser le fait que l'algorithme est déterministe.)

Votre approche de prise de randomisation n'est pas suffisante car certaines difficultés ne peuvent pas être surmontées par la randomisation.Mais il y a quelques modèles de relaxation de votre problème.

Certaines de celles-ci, et quelques détails à ma réponse peuvent être trouvés dans le papier de Susanne Albers, Arindam Khan et Leon Ladewig nommé "Algorithmes en ligne améliorés pour le bon de sac et l'écart dans le mode de commande aléatoire" (voir la section 1.1).