Parallel algorithm for Bounded Knapsack Problem (Dmitry Vyukov)

  • courseware
  • Algorithms and Complexity
  • Advanced Analysis
  • Intel TBB
  • tbb
  • knapsack
  • bounded knapsack problem
  • intel threading building blocks
  • dynamic programming
  • The included code and solution write-up provides a parallel solution for the bounded knapsack problem, as described in the included problem description text file. The included write-up gives an overview of a dynamic programming algorithm to choose between possible solutions. In order to reduce the computational complexity, some preprocessing techniques are applied as described in the write-up. The parallelization of the dynamic programming portion of the algorithm was found to be untenable. However, the preprocessing steps offered enough independent work to make parallelization worthwhile. Intel Threading Building Blocks (TBB) is used for implementing the parallelism within the preprocessing tasks. The code was intended for Windows OS and includes Microsoft Visual Studio solution and project files to build the application.
    DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment.

    Sono disponibili dei download in Creative Commons License license. Scarica ora
    Per informazioni più dettagliate sulle ottimizzazioni basate su compilatore, vedere il nostro Avviso sull'ottimizzazione.