Algorithmic Burglar

Mathematical solution:

Rhodium and Silicon have the highest value per pound at $39. Since all the missing weights are above 38 pounds, any combination of Rhodium and Silicon bars will get us to a wanted missing amount of metal, because 19 is 1 mod 3, so if the missing amount is 1 more than a multiple of three, we just have one multiple of 19, and if the missing amount is 2 more than a multiple of 3, then we have two multiples of 19. The rest of the missing metal can be stolen through silicon bars.

Thus the maximum value of missing metal is just the sum of all of the missing metals multiplied by $39, and that's 153153 so the answer is $\boxed{153}$ .

It should be obvious that the maximum amount of obtainable money from $N$ pounds is the maximum possible value of obtainable money from $N-i$ pounds(where $i$ is the cost of any one of the listed bars in the weight-dollar values) plus the cost of the bar itself.This is a recursive relation which can be optimized using Dynamic Programming.

Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#Dynamic programming once again!
Bars = [(2,57),(5,191),(14,417),(17,231),(19,741),(13,139),(1,28),(3,117),(5,13),(11,9),(19,18)]
Max = {0:0} 
Pounds = 0
while Pounds <= 2000:
    Pounds += 1
    Largest = 0
    for bar in Bars:
        Remaining = Pounds - bar[0]
        if Remaining < 0:
            continue
        else:
            Value = Max[Remaining] + bar[1]
            if Value > Largest:
                Largest = Value
    Max[Pounds] = Largest
V = Max[55]+Max[72]+Max[99]+Max[212]+Max[511]+Max[1239]+Max[1739]
print V % 1000

This is classical fractional knapsack problem.

Below is the C++ code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

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

int wt[] = {2, 5, 14, 17, 19, 13, 1, 3, 5, 11, 19};
int price[] = {57, 191, 417, 231, 741, 139, 28, 117, 13, 9, 18};
int N = 11;

int knapsackDP(int W)
{
    int dp[2][W+1] = {0};
    for(int n = 0; n <= N; n++)
    {
        for(int w = 0; w <= W; w++)
        {
             if(n == 0 || w == 0)
                 dp[1][w] = 0;
             else
             {
                  int inc = 0, exc = 0;
                  if(wt[n-1] <= w)
                        inc = price[n-1] + dp[1][w - wt[n-1]];
                  exc = dp[0][w];
                  dp[1][w] = max(inc, exc);
              }
          }
          for(int i = 0; i <= W; i++)
               dp[0][i] = dp[1][i];
      }
      return dp[1][W];
}

int main() 
{
    int ans = 0;

    ans += knapsackDP(1739);
    ans += knapsackDP(72);
    ans += knapsackDP(212);
    ans += knapsackDP(55);
    ans += knapsackDP(511);
    ans += knapsackDP(1239);
    ans += knapsackDP(99);

    cout << ans << endl;
    return 0;
}