![]() Of the possible subsets of problems whose total point values add up to 100, a knapsack algorithm would determine which subset gives each student the highest possible score. The students are asked to answer all of the questions to the best of their abilities. Feuerman and Weiss proposed a system in which students are given a heterogeneous test with a total of 125 possible points. different questions are worth different point values- it is more difficult to provide choices. We will reduce the Exact Cover by 3-Sets (EC3S) problem to Knapsack. which bits of a to make 1 and which 0), and then it only takes a polynomial number of steps to check whether we met the goal G. However, on tests with a heterogeneous distribution of point values-i.e. Knapsack is certainly in NP, since we can guess which toys to take (i.e. For example, if an exam contains 12 questions each worth 10 points, the test-taker need only answer 10 questions to achieve a maximum possible score of 100 points. For small examples it is a fairly simple process to provide the test-takers with such a choice. One early application of knapsack algorithms was in the construction and scoring of tests in which the test-takers have a choice as to which questions they answer. Knapsack problems appear in real-world decision-making processes in a wide variety of fields, such as finding the least wasteful way to cut raw materials, selection of capital investments and financial portfolios, selection of assets for asset-backed securitization, and generating keys for the Merkle–Hellman knapsack cryptosystem. A 1998 study of the Stony Brook University Algorithm Repository showed that, out of 75 algorithmic problems, the knapsack problem was the 18th most popular and the 4th most needed after kd-trees, suffix trees, and the bin packing problem.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |