首页 | 本学科首页   官方微博 | 高级检索  
     检索      


An adaptive stochastic knapsack problem
Authors:Kai Chen  Sheldon M Ross
Institution:Epstein Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, CA 90089, United States
Abstract:We consider a stochastic knapsack problem in which the event of overflow results in the problem ending with zero return. We assume that there are n   types of items available where each type has infinite supply. An item has an exponentially distributed random weight with a known mean depending on its type and the item’s value is proportional to its weight with a given factor depending on the item’s type. We have to make a decision on each stage whether to stop, or continue to put an item of a selected type in the knapsack. An item’s weight is learned when placed to the knapsack. The objective of this problem is to find a policy that maximizes the expected total values. Using the framework of dynamic programming, the optimal policy is found when n=2n=2 and a heuristic policy is suggested for n>2n>2.
Keywords:Decision process  Dynamic programming  Stochastic knapsack
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号