蟻本 - 動的計画法

int dp[MAX_N + 1][MAX_W + 1];

void solve() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= W; j++) {
      if (j < w[i]) {
        dp[i+1][j] = dp[i][j];
      } else {
        dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i]);
      }
    }
  }
  printf("%d\n", dp[n][W]);
}

MAX_N=100
MAX_W=10**4
dp = Array.new(MAX_N+1).map{Array.new(MAX_W+1, 0)}
n = 4
w = 5
wv_h = [ {2=>3}, {1=>2}, {3=>4}, {2=>2} ]

def solve(n, w, wv_h, dp)
  for i in 0...n
    for j in 0..w
      if j < wv_h[i].keys.first
        dp[i+1][j] = dp[i][j]
      else
        dp[i+1][j] = [dp[i][j], dp[i][j-wv_h[i].keys.first]+wv_h[i].values.first].max
      end
    end
  end
  puts "%d" % dp[n][w]
end

solve(n, w, wv_h, dp)

int dp[MAX_N + 1][MAX_N * MAX_V + 1];

void solve() {
  fill(dp[0], dp[0] + MAX_N * MAX_V + 1, INF);
  dp[0][0] = 0;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= MAX_N * MAX_V; j++) {
      if (j < v[i]) {
        dp[i+1][j] = dp[i][j];
      } else {
        dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]]+w[i]);
      }
    }
  }

  printf("%d\n", dp[n][W]);
}

$MAX_N=100
$MAX_V=100
INF=10**5
dp = Array.new($MAX_N+1).map{Array.new($MAX_N*$MAX_V+1, INF)}

n = 4
w = 5
wv_h = [ {2=>3}, {1=>2}, {3=>4}, {2=>2} ]

def solve(n, w, wv_h, dp)
  dp[0][0] = 0
  for i in 0...n
    for j in 0..($MAX_N*$MAX_V)
      if j < wv_h[i].keys.first
        dp[i+1][j] = dp[i][j]
      else
        dp[i+1][j] = [dp[i][j], dp[i][j-wv_h[i].values.first] + wv_h[i].keys.first].min
      end
    end
  end
  ans = 0
  for i in 0..$MAX_N*$MAX_V
    ans = i if dp[n][i] <= w
  end
  puts ans
end

solve(n, w, wv_h, dp)