The Bounded Knapsack Problem involves selecting items to maximize total value within a given weight capacity W. Each of the n item types has a specified value vi, weight wi, and a supply count mi.

Naive Implementation

A straightforward approach extends the standard 0-1 knapsack dynamic programming algorithm by adding an inner loop to process the count of each item. This results in a time complexity of O(W * Σmi), which is inefficient for large input constraints.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
   int n, W;
   std::cin >> n >> W;
   std::vector<int> dp(W + 1, 0);
   for (int i = 0; i < n; ++i) {
       int val, weight, count;
       std::cin >> val >> weight >> count;
       for (int j = W; j >= 0; --j) {
           for (int k = 1; k <= count && k * weight <= j; ++k) {
               dp[j] = std::max(dp[j], dp[j - k * weight] + k * val);
           }
       }
   }
   std::cout << dp[W] << std::endl;
   return 0;
}

Binary Splitting Optimization

To optimize, we decompose the total count mi of each item into a set of smaller bundles whose sizes are powers of two (e.g., 1, 2, 4, ...). Any integer up to mi can be represented by a sum of these powers, plus a remainder term. This transformation allows us to treat the bounded knapsack as a collection of 0-1 kanpsack items, reducing the complexity to O(W * Σlog(mi)).

#include <iostream>
#include <vector>
#include <algorithm>

void solve_01(std::vector<int>& dp, int val, int weight, int capacity) {
   for (int j = capacity; j >= weight; --j) {
       dp[j] = std::max(dp[j], dp[j - weight] + val);
   }
}

int main() {
   int n, W;
   std::cin >> n >> W;
   std::vector<int> dp(W + 1, 0);

   for (int i = 0; i < n; ++i) {
       int val, weight, count;
       std::cin >> val >> weight >> count;

       // Binary decomposition of count
       for (int k = 1; count > 0; k <<= 1) {
           int take = std::min(k, count);
           solve_01(dp, take * val, take * weight, W);
           count -= take;
       }
   }
   std::cout << dp[W] << std::endl;
   return 0;
}