Skip to content

Instantly share code, notes, and snippets.

@lh0x00
Last active September 15, 2020 06:57
Show Gist options
  • Save lh0x00/f5d4530fe0631e971af17fefc8bcaea8 to your computer and use it in GitHub Desktop.
Save lh0x00/f5d4530fe0631e971af17fefc8bcaea8 to your computer and use it in GitHub Desktop.
function get_max_value(
k: number,
n: number,
weights: number[],
values: number[],
): number {
let max_value = 0
const ratios = {} as { [i: number]: number }
for (let i = 0; i < n; i++) {
ratios[i] = values[i] / weights[i]
}
let total_weight = 0
const ordered = Object.entries(ratios).sort((a, b) => b[1] - a[1])
ordered.forEach(([idx, value]) => {
if (total_weight + weights[idx] <= k) {
max_value += values[idx]
total_weight += weights[idx]
}
})
return max_value
}
get_max_value(10, 6, [5, 7, 6, 1, 2, 3], [1, 3, 2, 2, 3, 4])
@lh0x00
Copy link
Author

lh0x00 commented Sep 14, 2020

As Javascript:

function get_max_value(
  k,
  n,
  weights,
  values,
) {
  let max_value = 0

  const ratios = {}
  for (let i = 0; i < n; i++) {
    ratios[i] = values[i] / weights[i]
  }

  let total_weight = 0

  const ordered = Object.entries(ratios).sort((a, b) => b[1] - a[1])
  ordered.forEach(([idx, value]) => {
    if (total_weight + weights[idx] <= k) {
      max_value += values[idx]
      total_weight += weights[idx]
    }
  })

  return max_value
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment