Knapsack problem

0–1 Knapsack problem

C++ solution

/*
Time complexity O(NW)
Space complexity O(NW)
*/
#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
int dp[1001][1001];
/*
w1 w2 w3
      for w3, we can take or not take
      take dp[w - w3][3 - 1] + v3
      not take dp[w][3-1]
*/
int knapsack(vector<int>& values, vector<int>& ws, int w, int i) {
    if (i < 0 || w <= 0) return 0;
    if (dp[w][i] != -1) return dp[w][i];
    int take = w >= ws[i] ? knapsack(values, ws, w - ws[i], i - 1) + values[i] : -1;
    int notTake = knapsack(values, ws, w, i - 1);
    return dp[w][i] = max(take, notTake);
}
int main() {
    int n, w;
    cin >> n;
    cin >> w;
    vector<int>values(n);
    vector<int> ws(n);
    for (int i = 0; i < n; ++ i) {
        cin >> ws[i];
        cin >> values[i];
    }
    memset(dp, -1, sizeof(dp));
    cout << knapsack(values, ws, w, n - 1) << endl;
    return 0;
}

M array partitions

http://acmgnyr.org/year2016/problems/C-M-ary.pdf

#include<bits/stdc++.h>
using namespace std;
int dp[10010][32];
int main()
{
    memset(dp, 0, sizeof(dp));
 int n, k;
 cin >> k >> n;
 vector<int> val;
 int i = 0;
 int this_v;
 while (true) {
     this_v = pow(k, i++);
     if (this_v <= n) {
         val.push_back(this_v);
     } else break;
 }
 const int m = val.size();
 dp[0][0] = 1;
 // O(32*32*n )
 for (int i = 0; i <= n; ++i){
     for (int j = 0; j < m ;++j){
         for (int l = j; l < m; ++l){
             int this_v = i + pow(k, l);
             if (this_v <= n) {
                 dp[this_v][l] += dp[i][j];
             } 
         }
     }
 }
 int ret = 0;
 for (int i = 0; i<32; ++i) {
     ret += dp[n][i];
 }
 cout << ret << endl;
 return 0;
}