Stack Overflow Coins DP Challenge

fast.cpp

#include <bits/stdc++.h>
using namespace std;


void solve() {
  int n, target;
  cin >> n >> target;
  vector<int> coins(n);
  for (int i = 0; i < n; i++) {
    cin >> coins[i];
  }
  vector<int> coin_uses(n);
  for (int i = 0; i < n; i++) {
    cin >> coin_uses[i];
  }

  vector<int> dp(target+1, INT_MAX);
  dp[0] = 0;

  for (int coin = 0; coin < n; coin++) {
    vector<int> dp_new(dp);

    int value = coins[coin];
    if (value > target) {
      // We will never use it if it already takes us over the target
      continue;
    }
    for (int a = 0; a < value; a++) {
      // Subgroup a, a+value, a+2*value, ...
      deque<int> sliding_window; // holds the dp[i] that we are interested in
                                 // front=earliest/lowest index/best, back=latest/highest index/worst
      if (dp[a] != INT_MAX) {
        sliding_window.push_back(a); // start off with the lowest one in our subgroup
      }
      for (int uses = 1; true; uses++) {
        // This iterates through a+value, a+2*value, ...
        int new_index = a + uses*value;
        if (new_index > target) {
          break;
        }

        // Update: get rid of the front if it is too old
        if (!sliding_window.empty()) {
          int front = sliding_window.front();
          if (front < new_index - coin_uses[coin] * value) {
            sliding_window.pop_front();
          }
        }
        // Update: add the new one at the back, but delete all the worse ones
        int value_of_current = dp[new_index];
        if (value_of_current != INT_MAX) { // Only add the new one as a candidate if it's possible to get to, of course
          while (!sliding_window.empty()) {
            int back = sliding_window.back();
            // Current value: 5
            // == 4 from 1 value ago (it would be 5 now)
            // == 3 from 2 values ago
            // etc
            int dist = (new_index - back) / value;
            if (value_of_current <= dp[back] + dist) {
              sliding_window.pop_back();
            } else {
              break;
            }
          }
          sliding_window.push_back(new_index);
        }
        // Update ourselves
        if (!sliding_window.empty()) {
          assert(dp[sliding_window.front() != INT_MAX]);
          int possible_new_value = dp[sliding_window.front()] + (new_index - sliding_window.front()) / value;
          dp_new[new_index] = min(dp_new[new_index], possible_new_value);
        }
      }
    }

    dp = dp_new;
  }

  if (dp[target] == INT_MAX) {
    cout << "impossible\n";
  } else {
    cout << dp[target] << "\n";
  }
}






int main() {
  int T;
  cin >> T;
  while (T--)  solve();
  return 0;
}

slow.cpp

#include <bits/stdc++.h>
using namespace std;


void solve() {
  int n, target;
  cin >> n >> target;
  vector<int> coins(n);
  for (int i = 0; i < n; i++) {
    cin >> coins[i];
  }
  vector<int> uses(n);
  for (int i = 0; i < n; i++) {
    cin >> uses[i];
  }

  // dp[amount] = minimum number of coins needed to reach :amount:
  // with combinations of coins we have seen so far
  vector<int> dp(target+1, INT_MAX);
  dp[0] = 0;

  // We are going to discover a new coin one at a time
  for (int coin = 0; coin < n; coin++) {
    vector<int> dp_new(dp);   // (We keep a copy of the old array because we need those values)
    // Starting at $x, we will try using 1 of our new coin to go to $x+value
    // So the optimal way to get to $x+value is either what we had before (dp_new[i]) or the new way (dp[x]+1)
    // And 2 of our new coins to go to $x+2*value, and so on up to the limit of uses[coin]
    for (int x = 0; x <= target; x++) {
      if (dp[x] == INT_MAX)  continue;  // Because we can't start at $x
      // Try x+value, x+2*value, ...
      for (int count = 1; count <= uses[coin]; count++) {
        // $i is the new value we can get from $x + count*value
        int i = x + count*coins[coin];
        if (i > target)  continue;
        dp_new[i] = min(dp_new[i], dp[x] + count);
      }
    }
    dp = dp_new;
  }

  if (dp[target] == INT_MAX) {
    cout << "impossible\n";
  } else {
    cout << dp[target] << "\n";
  }
}






int main() {
  int T;
  cin >> T;
  while (T--)  solve();
  return 0;
}

test_case_converter.py

all_tcs = [
  [[1],[100],73],
  [[1,5],[3,2],14],
  [[1,5,10],[10,2,1],23],
  [[2,4],[10,10],7],
  [[3,7],[10,10],24],
  [[1,3,4],[5,5,1],6],
  [[1,5,10],[2,1,1],18],
  [[1,7,10],[10,1,1],14],
  [[4,5,9],[5,5,5],18],
  [[6,9,20],[5,5,5],43],
  [[5,10],[0,10],50],
  [[1,2,5],[0,0,10],10],
  [[7],[3],21],
  [[7],[2],21],
  [[1,3,5],[1,1,1],8],
  [[1,2,5,10],[1,1,1,1],18],
  [[2,3,7],[10,10,1],14],
  [[1,4,6,9],[2,2,2,2],18],
  [[5,11,17],[10,10,10],34],
  [[1,8,15],[100,1,1],23],
  [[1,2],[10,5],7],
  [[1,3],[5,2],8],
  [[2,5],[5,2],12],
  [[1,4,6],[5,1,1],10],
  [[1,3,9],[3,1,1],13],
  [[2,7,10],[5,1,1],17],
  [[1,2,5,10],[3,2,1,1],18],
  [[1,3,5],[2,2,1],11],
  [[1,2,5],[10,1,1],8],
  [[1,2,5,10],[10,2,1,1],19],
  [[3,4,7],[5,2,1],15],
  [[2,5,10],[3,2,1],20],
  [[1,2,3],[5,5,5],9],
  [[1,3,4,5],[2,2,1,1],12],
  [[2,3,5,8],[3,2,2,1],18],
  [[1,5,6],[5,2,1],14],
  [[1,2,4],[3,3,1],9],
  [[1,3,7],[2,2,1],10],
  [[2,4,6],[2,2,1],12],
  [[1,2,5],[1,1,1],7],
  [[3,5,8],[2,1,1],13],
  [[1,2,6],[3,1,1],8],
  [[2,3,5],[5,2,2],14],
  [[1,4,7],[3,1,1],12],
  [[1,3,6,9],[2,2,1,1],15],
  [[2,5,7],[1,1,1],10],
  [[1,2,5,10],[2,2,1,1],19],
  [[1,3,5,8],[3,2,2,1],17],
  [[2,4,6,9],[2,2,1,1],18],
  [[1,2,3,7],[3,2,1,1],13],
  [[1,3,5],[5,3,2],16],
  [[2,5,10],[2,1,1],17],
  [[1,4,6],[3,1,1],11],
  [[1,2,5],[10,1,1],14],
  [[3,7,11],[2,1,1],18],
  [[1,2,3,4],[2,2,2,1],9],
  [[1,5,10,20],[5,2,1,1],23],
  [[2,3,5,7],[2,2,1,1],15],
  [[1,4,5,6],[3,1,1,1],13],
  [[1,2,3,6],[2,2,1,1],10],
  [[1,3,5,9],[3,2,1,1],16],
  [[2,4,7,10],[2,1,1,1],18],
  [[1,2,5,8],[5,2,1,1],19],
  [[1,3,6,7],[2,2,1,1],14],
  [[1,2,4,5],[3,2,1,1],12],
  [[3,5,7,9],[2,1,1,1],15],
  [[1,2,3,5],[4,2,1,1],11],
  [[1,4,6,8],[2,2,1,1],16],
  [[2,3,5,9],[3,2,1,1],14],
  [[1,2,5,6],[3,2,1,1],13],
  [[1,3,4,7],[2,2,1,1],12],
  [[2,4,6,8],[2,2,1,1],14],
  [[1,2,3,7],[3,2,1,1],13],
  [[1,3,5,7],[2,2,1,1],12],
  [[2,4,5,9],[3,2,1,1],15],
  [[1,2,4,6],[2,2,1,1],11],
  [[1,3,5,8],[3,2,1,1],14],
  [[2,3,6,7],[2,2,1,1],13],
  [[1,2,5,10],[4,2,1,1],17],
  [[1,3,6,9],[3,2,1,1],15],
  [[2,5,7,10],[2,1,1,1],16],
  [[1,2,3,4],[5,2,1,1],12],
  [[1,3,5,6],[3,2,1,1],14],
  [[2,4,6,9],[2,2,1,1],15],
  [[1,2,3,7],[3,2,1,1],12],
  [[1,4,5,8],[2,2,1,1],14],
  [[2,3,5,7],[2,2,1,1],13],
  [[1,2,4,6],[3,2,1,1],15],
  [[1,3,5,9],[2,2,1,1],14],
  [[2,5,7,10],[2,1,1,1],17],
  [[1,2,3,6],[3,2,1,1],13],
  [[1,3,4,7],[2,2,1,1],12],
  [[2,4,6,8],[2,2,1,1],14],
  [[1,2,5,8],[3,2,1,1],15],
  [[1,3,6,9],[3,2,1,1],16],
  [[2,3,5,9],[2,2,1,1],15],
  [[1,2,3,4],[4,2,1,1],11],
  [[1,3,5,7],[2,2,1,1],13],
  [[2,4,6,9],[2,2,1,1],14],
  [[1,2,5,6],[3,2,1,1],12]
]


if __name__ == '__main__':
  n = len(all_tcs)
  print(n)
  for tc in all_tcs:
    print(len(tc[0]))
    print(tc[2])
    print(' '.join(str(x) for x in tc[0]))
    print(' '.join(str(x) for x in tc[1]))

zzz_integer_programming_killer.txt

# n = 500 coins (because integer programming is exponential in the number of coins)
# target = 50,000 $
# max uses <= 20

# On my PC, runtimes are:
# Slow DP: 2.6s
# Fast DP: 0.2s
# Python Z3: Control-C'd after 50 min
#   Different linear programmers with different heuristics may perform slightly better or worse.

# stdin format
1
500
50000
2129 1088 740 405 34 2021 960 1891 1836 118 922 2007 291 1473 1685 24 1585 1086 741 300 1821 2358 1069 1115 967 852 2242 638 2241 2053 1878 2240 255 342 2408 1484 2337 1749 1096 1055 780 1150 1692 237 2396 2278 295 2292 398 617 594 1187 1250 1975 626 2409 2197 100 231 137 502 1763 335 106 499 1232 1443 508 2342 1259 402 890 1655 957 1811 1406 1278 127 1368 1482 1020 2123 364 2455 1606 964 1829 1958 1755 1447 870 784 181 865 1844 1301 1537 722 1667 727 2245 1296 251 712 1868 1689 684 605 633 135 945 2260 130 2169 553 864 2231 1270 170 2451 1589 983 1285 120 1808 2480 2387 1305 1724 1730 1738 782 1059 1735 2067 842 1394 1222 490 467 702 1901 2212 1877 511 1315 1766 1961 708 1057 2488 673 245 2379 110 2269 191 1563 825 1007 1432 204 33 834 745 1310 1634 95 2193 1614 801 1839 1480 1449 2464 1815 2360 728 1322 58 1612 1691 1081 1873 221 1350 770 1785 1018 1391 769 65 1282 1477 1422 547 491 1604 2100 1574 121 891 1075 489 56 132 2238 14 376 737 2453 846 1095 1907 889 901 1348 210 2190 2495 1179 2347 456 346 2470 1597 243 1022 177 2375 277 777 337 1407 1603 2054 1265 2150 57 452 454 1365 1565 64 675 1141 869 2141 13 1524 1023 391 2134 2339 2219 1917 1635 1792 1091 996 1191 11 2460 1897 1199 2233 528 832 908 71 1674 2452 1101 1064 930 868 621 1360 139 1146 274 1544 965 1223 645 1221 2206 971 1037 2350 1438 2177 1431 517 2031 660 220 155 2442 1281 2313 174 1402 932 2226 1137 1242 2413 2491 1582 115 126 2087 521 367 1709 89 407 399 703 1411 815 1562 1070 1945 2046 2308 1722 1254 758 1076 1054 567 748 989 1936 1668 412 1971 1405 381 1913 751 1219 1358 433 378 416 1727 336 992 114 1006 1853 506 988 1412 853 366 15 2289 2149 2262 2390 995 818 1434 1583 2064 991 334 1493 2153 2404 588 2418 1381 1973 1598 1485 1903 2096 2431 668 148 1941 30 1740 236 1327 951 614 1620 2221 329 604 1235 733 1013 436 2068 1864 944 1061 217 193 1082 1680 1014 1693 2448 2295 1883 254 328 827 2205 1466 2185 2131 1332 2456 1666 845 1161 572 249 706 1894 1166 1601 2142 2450 379 403 206 1144 1898 1138 1704 1798 72 1809 1511 2066 2346 582 787 1133 269 304 482 732 1244 942 298 1616 806 1784 463 2044 933 1984 1120 2215 579 2178 1122 1617 459 530 2030 2483 473 630 200 9 358 1474 1079 1911 1818 1168 285 1875 2287 826 1972 2040 775 384 1217 821 16 972 1134 527 2101 52 514
4 18 6 3 18 3 4 12 7 15 20 4 17 16 1 15 8 15 13 5 4 12 6 19 17 1 6 2 1 15 1 17 4 7 9 20 2 5 13 6 15 1 15 7 8 18 17 15 13 10 3 3 16 2 16 8 7 17 8 7 12 4 20 10 1 17 1 10 3 7 6 16 12 5 2 13 7 3 8 2 10 9 5 14 9 14 6 7 13 12 17 11 7 17 6 1 17 18 4 5 3 9 2 3 9 19 16 13 18 2 2 2 11 18 5 12 1 5 14 11 15 5 3 5 8 9 11 7 1 2 5 15 19 14 16 20 1 8 6 5 9 14 8 2 2 2 1 9 1 7 11 1 18 6 14 5 5 3 14 15 6 4 7 15 13 12 12 7 7 12 6 19 2 12 6 15 10 6 13 17 9 8 20 17 3 20 17 4 16 17 1 16 15 17 14 3 19 2 16 5 17 17 13 5 9 9 4 11 5 7 20 13 20 13 5 9 18 19 10 8 10 18 19 17 18 12 13 11 3 1 16 17 2 6 7 9 11 17 13 17 13 1 8 15 11 17 2 14 11 19 11 14 11 14 7 14 12 14 11 12 1 9 18 9 9 5 14 9 13 1 8 18 19 10 12 4 15 12 16 9 17 11 16 6 3 3 4 1 3 14 4 4 17 9 13 5 18 5 1 7 3 5 14 14 9 14 2 6 7 10 18 14 15 6 12 8 1 3 5 1 14 10 12 9 7 7 16 19 8 12 17 7 11 20 6 4 4 14 5 12 17 20 11 1 10 1 11 19 7 17 20 7 12 8 20 15 15 3 8 10 17 8 8 19 6 14 11 6 13 16 6 14 16 9 2 20 12 6 12 12 18 7 9 1 7 13 3 18 18 9 20 3 11 6 2 4 11 1 20 10 18 8 20 8 18 5 19 14 9 14 13 11 13 13 7 19 11 14 12 7 5 19 19 19 6 4 16 10 9 8 19 10 12 10 14 4 7 12 3 11 4 10 7 17 20 2 20 4 5 17 12 5 5 11 16 14 9 9 2 15 17 17 4 9 19 4 15 2 19 10 11 5 18 1 7 16 9 1 19 20 12 1 18 15 10 16 10 10 13 2 14 14 18 17 10 9 20 17 17 6

# json/python format
[[2129, 1088, 740, 405, 34, 2021, 960, 1891, 1836, 118, 922, 2007, 291, 1473, 1685, 24, 1585, 1086, 741, 300, 1821, 2358, 1069, 1115, 967, 852, 2242, 638, 2241, 2053, 1878, 2240, 255, 342, 2408, 1484, 2337, 1749, 1096, 1055, 780, 1150, 1692, 237, 2396, 2278, 295, 2292, 398, 617, 594, 1187, 1250, 1975, 626, 2409, 2197, 100, 231, 137, 502, 1763, 335, 106, 499, 1232, 1443, 508, 2342, 1259, 402, 890, 1655, 957, 1811, 1406, 1278, 127, 1368, 1482, 1020, 2123, 364, 2455, 1606, 964, 1829, 1958, 1755, 1447, 870, 784, 181, 865, 1844, 1301, 1537, 722, 1667, 727, 2245, 1296, 251, 712, 1868, 1689, 684, 605, 633, 135, 945, 2260, 130, 2169, 553, 864, 2231, 1270, 170, 2451, 1589, 983, 1285, 120, 1808, 2480, 2387, 1305, 1724, 1730, 1738, 782, 1059, 1735, 2067, 842, 1394, 1222, 490, 467, 702, 1901, 2212, 1877, 511, 1315, 1766, 1961, 708, 1057, 2488, 673, 245, 2379, 110, 2269, 191, 1563, 825, 1007, 1432, 204, 33, 834, 745, 1310, 1634, 95, 2193, 1614, 801, 1839, 1480, 1449, 2464, 1815, 2360, 728, 1322, 58, 1612, 1691, 1081, 1873, 221, 1350, 770, 1785, 1018, 1391, 769, 65, 1282, 1477, 1422, 547, 491, 1604, 2100, 1574, 121, 891, 1075, 489, 56, 132, 2238, 14, 376, 737, 2453, 846, 1095, 1907, 889, 901, 1348, 210, 2190, 2495, 1179, 2347, 456, 346, 2470, 1597, 243, 1022, 177, 2375, 277, 777, 337, 1407, 1603, 2054, 1265, 2150, 57, 452, 454, 1365, 1565, 64, 675, 1141, 869, 2141, 13, 1524, 1023, 391, 2134, 2339, 2219, 1917, 1635, 1792, 1091, 996, 1191, 11, 2460, 1897, 1199, 2233, 528, 832, 908, 71, 1674, 2452, 1101, 1064, 930, 868, 621, 1360, 139, 1146, 274, 1544, 965, 1223, 645, 1221, 2206, 971, 1037, 2350, 1438, 2177, 1431, 517, 2031, 660, 220, 155, 2442, 1281, 2313, 174, 1402, 932, 2226, 1137, 1242, 2413, 2491, 1582, 115, 126, 2087, 521, 367, 1709, 89, 407, 399, 703, 1411, 815, 1562, 1070, 1945, 2046, 2308, 1722, 1254, 758, 1076, 1054, 567, 748, 989, 1936, 1668, 412, 1971, 1405, 381, 1913, 751, 1219, 1358, 433, 378, 416, 1727, 336, 992, 114, 1006, 1853, 506, 988, 1412, 853, 366, 15, 2289, 2149, 2262, 2390, 995, 818, 1434, 1583, 2064, 991, 334, 1493, 2153, 2404, 588, 2418, 1381, 1973, 1598, 1485, 1903, 2096, 2431, 668, 148, 1941, 30, 1740, 236, 1327, 951, 614, 1620, 2221, 329, 604, 1235, 733, 1013, 436, 2068, 1864, 944, 1061, 217, 193, 1082, 1680, 1014, 1693, 2448, 2295, 1883, 254, 328, 827, 2205, 1466, 2185, 2131, 1332, 2456, 1666, 845, 1161, 572, 249, 706, 1894, 1166, 1601, 2142, 2450, 379, 403, 206, 1144, 1898, 1138, 1704, 1798, 72, 1809, 1511, 2066, 2346, 582, 787, 1133, 269, 304, 482, 732, 1244, 942, 298, 1616, 806, 1784, 463, 2044, 933, 1984, 1120, 2215, 579, 2178, 1122, 1617, 459, 530, 2030, 2483, 473, 630, 200, 9, 358, 1474, 1079, 1911, 1818, 1168, 285, 1875, 2287, 826, 1972, 2040, 775, 384, 1217, 821, 16, 972, 1134, 527, 2101, 52, 514], [4, 18, 6, 3, 18, 3, 4, 12, 7, 15, 20, 4, 17, 16, 1, 15, 8, 15, 13, 5, 4, 12, 6, 19, 17, 1, 6, 2, 1, 15, 1, 17, 4, 7, 9, 20, 2, 5, 13, 6, 15, 1, 15, 7, 8, 18, 17, 15, 13, 10, 3, 3, 16, 2, 16, 8, 7, 17, 8, 7, 12, 4, 20, 10, 1, 17, 1, 10, 3, 7, 6, 16, 12, 5, 2, 13, 7, 3, 8, 2, 10, 9, 5, 14, 9, 14, 6, 7, 13, 12, 17, 11, 7, 17, 6, 1, 17, 18, 4, 5, 3, 9, 2, 3, 9, 19, 16, 13, 18, 2, 2, 2, 11, 18, 5, 12, 1, 5, 14, 11, 15, 5, 3, 5, 8, 9, 11, 7, 1, 2, 5, 15, 19, 14, 16, 20, 1, 8, 6, 5, 9, 14, 8, 2, 2, 2, 1, 9, 1, 7, 11, 1, 18, 6, 14, 5, 5, 3, 14, 15, 6, 4, 7, 15, 13, 12, 12, 7, 7, 12, 6, 19, 2, 12, 6, 15, 10, 6, 13, 17, 9, 8, 20, 17, 3, 20, 17, 4, 16, 17, 1, 16, 15, 17, 14, 3, 19, 2, 16, 5, 17, 17, 13, 5, 9, 9, 4, 11, 5, 7, 20, 13, 20, 13, 5, 9, 18, 19, 10, 8, 10, 18, 19, 17, 18, 12, 13, 11, 3, 1, 16, 17, 2, 6, 7, 9, 11, 17, 13, 17, 13, 1, 8, 15, 11, 17, 2, 14, 11, 19, 11, 14, 11, 14, 7, 14, 12, 14, 11, 12, 1, 9, 18, 9, 9, 5, 14, 9, 13, 1, 8, 18, 19, 10, 12, 4, 15, 12, 16, 9, 17, 11, 16, 6, 3, 3, 4, 1, 3, 14, 4, 4, 17, 9, 13, 5, 18, 5, 1, 7, 3, 5, 14, 14, 9, 14, 2, 6, 7, 10, 18, 14, 15, 6, 12, 8, 1, 3, 5, 1, 14, 10, 12, 9, 7, 7, 16, 19, 8, 12, 17, 7, 11, 20, 6, 4, 4, 14, 5, 12, 17, 20, 11, 1, 10, 1, 11, 19, 7, 17, 20, 7, 12, 8, 20, 15, 15, 3, 8, 10, 17, 8, 8, 19, 6, 14, 11, 6, 13, 16, 6, 14, 16, 9, 2, 20, 12, 6, 12, 12, 18, 7, 9, 1, 7, 13, 3, 18, 18, 9, 20, 3, 11, 6, 2, 4, 11, 1, 20, 10, 18, 8, 20, 8, 18, 5, 19, 14, 9, 14, 13, 11, 13, 13, 7, 19, 11, 14, 12, 7, 5, 19, 19, 19, 6, 4, 16, 10, 9, 8, 19, 10, 12, 10, 14, 4, 7, 12, 3, 11, 4, 10, 7, 17, 20, 2, 20, 4, 5, 17, 12, 5, 5, 11, 16, 14, 9, 9, 2, 15, 17, 17, 4, 9, 19, 4, 15, 2, 19, 10, 11, 5, 18, 1, 7, 16, 9, 1, 19, 20, 12, 1, 18, 15, 10, 16, 10, 10, 13, 2, 14, 14, 18, 17, 10, 9, 20, 17, 17, 6], 50000]

# Answer: 21


---


# Here's another test case with only n = 30 coins, target = 30,000 $, and max uses <= 100.
# I control-C'd the Python Z3 after 6 minutes of no solution.
# In contrast, the fast DP runs in milliseconds on this input.
# I believe "dense" inputs like these where lots of possible solution paths exist (compared to my first post where the solution was basically pick a bunch of the highest valued coin and then pad the rest) challenge integer programmers much more.

1
30
30000
18 246 86 227 95 68 74 78 31 38 144 280 72 2 14 224 217 274 48 104 170 146 33 151 135 212 96 205 67 207
3 42 69 67 50 6 93 47 76 48 8 57 63 83 25 19 73 5 7 55 85 59 37 93 80 85 51 59 39 88

[[18, 246, 86, 227, 95, 68, 74, 78, 31, 38, 144, 280, 72, 2, 14, 224, 217, 274, 48, 104, 170, 146, 33, 151, 135, 212, 96, 205, 67, 207], [3, 42, 69, 67, 50, 6, 93, 47, 76, 48, 8, 57, 63, 83, 25, 19, 73, 5, 7, 55, 85, 59, 37, 93, 80, 85, 51, 59, 39, 88], 30000]


---


# Z3 runtime analysis on different inputs

# n = 10, target = 10,000, max uses <= 100
[[36, 1, 43, 30, 4, 77, 16, 95, 29, 14], [23, 94, 64, 98, 49, 78, 12, 33, 39, 18], 10000]
0.99s

# n = 11, target = 11,000, max uses <= 100
[[43, 37, 67, 99, 12, 47, 41, 21, 58, 98, 56], [21, 10, 60, 61, 30, 54, 41, 18, 95, 57, 26], 11000]
0.86s  # some variance

# n = 12, target = 12,000
[[25, 108, 76, 42, 97, 55, 22, 20, 83, 88, 101, 89], [53, 64, 57, 11, 77, 80, 78, 12, 60, 28, 85, 68], 12000]
Got bored and Control-C'd after 2 min

zzz_slow_dp_killer.txt

# n = 40 coins
# target = 1,000,000 $
# max uses <= 100

# On my PC, runtimes are:
# Fast DP: 0.4s
# Slow DP: 10.9s (asymptotically should be (max uses)x slower, here was ~20-30x slower since its constant factors are better)

# stdin format
1
40
1000000
3327 13991 13622 4784 9848 13004 7810 14807 8182 15907 13510 10982 13073 4394 9967 6648 4333 16575 4286 2999 8046 4271 7785 5636 5649 10167 11329 447 2506 13567 12865 14148 4317 8476 7197 14996 10979 6249 8456 16508
24 34 34 48 26 56 40 28 37 51 39 55 16 18 30 55 6 43 49 3 1 19 26 15 14 56 10 36 1 24 44 2 57 22 34 6 13 19 51 56

# json/python format
[[3327, 13991, 13622, 4784, 9848, 13004, 7810, 14807, 8182, 15907, 13510, 10982, 13073, 4394, 9967, 6648, 4333, 16575, 4286, 2999, 8046, 4271, 7785, 5636, 5649, 10167, 11329, 447, 2506, 13567, 12865, 14148, 4317, 8476, 7197, 14996, 10979, 6249, 8456, 16508], [24, 34, 34, 48, 26, 56, 40, 28, 37, 51, 39, 55, 16, 18, 30, 55, 6, 43, 49, 3, 1, 19, 26, 15, 14, 56, 10, 36, 1, 24, 44, 2, 57, 22, 34, 6, 13, 19, 51, 56], 1000000]

# Answer: 61