The bounded knapsack

def bounded_knapsack(weights, values, counts, cap):
    best = [0] * (cap + 1)
    for w, v, k in zip(weights, values, counts):
        size = 1
        while k > 0:
            take = min(size, k)                # a bundle of 'take' copies
            bw, bv = take * w, take * v
            for c in range(cap, bw - 1, -1):   # 0/1 update for the bundle
                best[c] = max(best[c], bv + best[c - bw])
            k -= take
            size *= 2
    return best[cap]

int bounded_knapsack(const std::vector<int>& weights, const std::vector<int>& values,
                     const std::vector<int>& counts, int cap) {
    std::vector<int> best(cap + 1, 0);
    for (size_t i = 0; i < weights.size(); ++i) {
        for (int size = 1, k = counts[i]; k > 0; size *= 2) {
            int take = std::min(size, k);                // a bundle of 'take' copies
            int bw = take * weights[i], bv = take * values[i];
            for (int c = cap; c >= bw; --c)              // 0/1 update for the bundle
                best[c] = std::max(best[c], bv + best[c - bw]);
            k -= take;
        }
    }
    return best[cap];
}

static int boundedKnapsack(int[] weights, int[] values, int[] counts, int cap) {
    int[] best = new int[cap + 1];
    for (int i = 0; i < weights.length; i++) {
        for (int size = 1, k = counts[i]; k > 0; size *= 2) {
            int take = Math.min(size, k);                // a bundle of 'take' copies
            int bw = take * weights[i], bv = take * values[i];
            for (int c = cap; c >= bw; c--)              // 0/1 update for the bundle
                best[c] = Math.max(best[c], bv + best[c - bw]);
            k -= take;
        }
    }
    return best[cap];
}

function boundedKnapsack(weights, values, counts, cap) {
    const best = new Array(cap + 1).fill(0);
    weights.forEach((w, i) => {
        for (let size = 1, k = counts[i]; k > 0; size *= 2) {
            const take = Math.min(size, k);              // a bundle of 'take' copies
            const bw = take * w, bv = take * values[i];
            for (let c = cap; c >= bw; c--)              // 0/1 update for the bundle
                best[c] = Math.max(best[c], bv + best[c - bw]);
            k -= take;
        }
    });
    return best[cap];
}

fn bounded_knapsack(weights: &[usize], values: &[i64], counts: &[usize], cap: usize) -> i64 {
    let mut best = vec![0i64; cap + 1];
    for i in 0..weights.len() {
        let (mut k, mut size) = (counts[i], 1);
        while k > 0 {
            let take = size.min(k);                      // a bundle of 'take' copies
            let (bw, bv) = (take * weights[i], take as i64 * values[i]);
            for c in (bw..=cap).rev() {                  // 0/1 update for the bundle
                best[c] = best[c].max(bv + best[c - bw]);
            }
            k -= take;
            size *= 2;
        }
    }
    best[cap]
}

boundedKnapsack :: [Int] -> [Int] -> [Int] -> Int -> Int
boundedKnapsack weights values counts cap = last (foldl add (replicate (cap + 1) 0) bundles)
  where
    -- k copies become bundles of 1, 2, 4, ... copies, so every count from 0 to k is a sum of bundles
    bundles = concat [ [(t * w, t * v) | t <- split k] | (w, v, k) <- zip3 weights values counts ]
    split k = go 1 k
      where go s r | r <= 0 = []
                   | otherwise = min s r : go (2 * s) (r - min s r)
    -- each bundle is then a 0/1 item
    add best (w, v) = [ if c >= w then max (row ! c) (v + row ! (c - w)) else row ! c | c <- [0 .. cap] ]
      where row = listArray (0, cap) best :: Array Int Int

def knapsack_bounded(weights, values, counts, capacity):
    best = [0] * (capacity + 1)
    for w, v, k in zip(weights, values, counts):
        size = 1
        while k > 0:
            take = min(size, k)                    # bundles 1, 2, 4, ..., remainder
            bw, bv = take * w, take * v
            for c in range(capacity, bw - 1, -1):  # 0/1 update for this bundle
                best[c] = max(best[c], bv + best[c - bw])
            k -= take
            size *= 2
    return best[capacity]

#include <algorithm>
#include <vector>

long long solve(const std::vector<int>& weights, const std::vector<int>& values, const std::vector<int>& counts, int capacity) {
    std::vector<long long> best(capacity + 1, 0);
    for (size_t i = 0; i < weights.size(); ++i) {
        for (long long k = counts[i], size = 1; k > 0; size *= 2) {
            long long take = std::min(size, k), bw = take * weights[i], bv = take * values[i];   // one bundle
            for (long long c = capacity; c >= bw; --c) best[c] = std::max(best[c], bv + best[c - bw]);
            k -= take;
        }
    }
    return best[capacity];
}

class Solution {
    public long knapsackBounded(int[] weights, int[] values, int[] counts, int capacity) {
        long[] best = new long[capacity + 1];
        for (int i = 0; i < weights.length; i++) {
            for (long k = counts[i], size = 1; k > 0; size *= 2) {
                long take = Math.min(size, k), bw = take * weights[i], bv = take * values[i];   // one bundle
                for (long c = capacity; c >= bw; c--) best[(int) c] = Math.max(best[(int) c], bv + best[(int) (c - bw)]);
                k -= take;
            }
        }
        return best[capacity];
    }
}

function knapsackBounded(weights, values, counts, capacity) {
  const best = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let k = counts[i], size = 1; k > 0; size *= 2) {
      const take = Math.min(size, k), bw = take * weights[i], bv = take * values[i];   // one bundle
      for (let c = capacity; c >= bw; c--) best[c] = Math.max(best[c], bv + best[c - bw]);
      k -= take;
    }
  }
  return best[capacity];
}

fn solve(weights: &[i64], values: &[i64], counts: &[i64], capacity: i64) -> i64 {
    let cap = capacity as usize;
    let mut best = vec![0i64; cap + 1];
    for i in 0..weights.len() {
        let (mut k, mut size) = (counts[i], 1i64);
        while k > 0 {
            let take = size.min(k);                         // one bundle
            let (bw, bv) = ((take * weights[i]) as usize, take * values[i]);
            if bw <= cap {
                for c in (bw..=cap).rev() {
                    best[c] = best[c].max(bv + best[c - bw]);
                }
            }
            k -= take;
            size *= 2;
        }
    }
    best[cap]
}

solve :: [Int] -> [Int] -> [Int] -> Int -> Int
solve weights values counts capacity = last (foldl addBundle (replicate (capacity + 1) 0) bundles)
  where
    -- every item split into bundles of 1, 2, 4, ... copies and a remainder
    split k size | k <= 0 = [] | otherwise = let t = min size k in t : split (k - t) (2 * size)
    bundles = [(t * w, t * v) | (w, v, k) <- zip3 weights values counts, t <- split k 1]
    addBundle best (bw, bv) = [if c >= bw then max b (bv + best !! (c - bw)) else b | (c, b) <- zip [0 ..] best]