Knapsack

• Time : O(kn)
• Space : O(k)

c++

int unboundedKnapsack(int k, vector<int> arr) {
    bool dp[2001] = {};
    dp[0] = true;
    for(auto& a : arr) {
        for(int i = a; i <= k; i++)
            dp[i] |= dp[i-a];
    }
    for(int i = k; i >= 0; i--)
        if(dp[i]) return i;
    return -1;    
}