Discounted {0-1} Knapsack Problem (DKP) adalah perluasan dari {0-1} Knapsack Problem (KP). Pada DKP akan dipilih sebuah himpunan kelompok-kelompok barang, dimana setiap kelompok terdiri dari tiga barang dan paling banyak satu dari tiga barang dapat dipilih. Barang ketiga dalam setiap kelompok merupakan gabungan dari barang pertama dan barang kedua. Dengan menggunakan konsep inti alternatif, DKP dapat dipartisi ke dalam beberapa submasalah berdasarkan tipe-tipe kasusnya (tidak berkorelasi, berkorelasi lemah, dan berkorelasi kuat). DKP yang telah dipartisi ini disebut partitioned DKP. Jika kasus dari DKP diketahui berkorelasi lemah atau berkorelasi kuat, maka dapat dilakukan partisi lebih lanjut lagi untuk memperbaiki efisiensi solusinya. Baik DKP maupun partitioned DKP dapat diselesaikan dengan menggunakan pemrograman dinamik. Berdasarkan percobaan numerik, penyelesaian partitioned DKP lebih efisien daripada penyelesaian DKP untuk semua kasus DKP, dengan tingkat efisiensi sekitar 11,79% untuk kasus tidak berkorelasi, 30,28% untuk kasus berkorelasi lemah, dan 41,84% untuk kasus berkorelasi kuat.

---

The Discounted {0-1} Knapsack Problem (DKP) is an extension of the {0-1} Knapsack Problem (KP). On DKP, it will be selected a set of item groups where each group consists of three items, and at most one of the three items can be selected. The third item in each groups is a combination of first item and second item. By using concept of alternative core, DKP can be partitioned to some sub problems based on types of DKP instances (uncorrelated, weakly correlated and strongly correlated).

If DKP is known as weakly correlated or strongly correlated, so it could be more partitioned for improving the solution efficiency. DKP and partitioned DKP could be solved by dynamic programming. Based on numerical experiments, solving partitioned DKP are more efficient than solving DKP for all cases of DKP, with efficiency level about 11.79% for uncorrelated instances, 30.28% for weakly correlated instances, and 41.84% for strongly correlated instances.