The unbounded knapsack

def knapsack_unbounded(weights, values, capacity):
    best = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(w, capacity + 1):       # upwards: the item may be reused
            best[c] = max(best[c], v + best[c - w])
    return best[capacity]

#include <algorithm>
#include <vector>

long long solve(const std::vector<int>& weights, const std::vector<int>& values, int capacity) {
    std::vector<long long> best(capacity + 1, 0);
    for (size_t i = 0; i < weights.size(); ++i)
        for (int c = weights[i]; c <= capacity; ++c)   // upwards: reuse allowed
            best[c] = std::max(best[c], values[i] + best[c - weights[i]]);
    return best[capacity];
}

class Solution {
    public long knapsackUnbounded(int[] weights, int[] values, int capacity) {
        long[] best = new long[capacity + 1];
        for (int i = 0; i < weights.length; i++)
            for (int c = weights[i]; c <= capacity; c++)   // upwards: reuse allowed
                best[c] = Math.max(best[c], values[i] + best[c - weights[i]]);
        return best[capacity];
    }
}

function knapsackUnbounded(weights, values, capacity) {
  const best = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++)
    for (let c = weights[i]; c <= capacity; c++)       // upwards: reuse allowed
      best[c] = Math.max(best[c], values[i] + best[c - weights[i]]);
  return best[capacity];
}

fn solve(weights: &[i64], values: &[i64], capacity: i64) -> i64 {
    let cap = capacity as usize;
    let mut best = vec![0i64; cap + 1];
    for (&w, &v) in weights.iter().zip(values) {
        for c in (w as usize)..=cap {                   // upwards: reuse allowed
            best[c] = best[c].max(v + best[c - w as usize]);
        }
    }
    best[cap]
}

import Data.Array

solve :: [Int] -> [Int] -> Int -> Int
solve weights values capacity = best ! capacity
  where
    items = zip weights values
    -- best ! c depends only on smaller capacities, so a lazy array computes it in the right order
    best = listArray (0, capacity) [maximum (0 : [v + best ! (c - w) | (w, v) <- items, w <= c]) | c <- [0 .. capacity]] :: Array Int Int