Skip to content

Instantly share code, notes, and snippets.

@lh0x00

lh0x00/get_max_value.ts

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.
Download ZIP

Revisions

  1. lh0x00 revised this gist Sep 15, 2020. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion get_max_value.ts
    View file
    Original file line number Diff line number Diff line change
    @@ -15,7 +15,7 @@ function get_max_value(

    const ordered = Object.entries(ratios).sort((a, b) => b[1] - a[1])
    ordered.forEach(([idx, value]) => {
    if (total_weight + weights[idx] < k) {
    if (total_weight + weights[idx] <= k) {
    max_value += values[idx]
    total_weight += weights[idx]
    }
  2. lh0x00 revised this gist Sep 15, 2020. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion get_max_value.ts
    View file
    Original file line number Diff line number Diff line change
    @@ -15,7 +15,7 @@ function get_max_value(

    const ordered = Object.entries(ratios).sort((a, b) => b[1] - a[1])
    ordered.forEach(([idx, value]) => {
    if (total_weight + weights[idx] < k && max_value < n) {
    if (total_weight + weights[idx] < k) {
    max_value += values[idx]
    total_weight += weights[idx]
    }
  3. lh0x00 created this gist Sep 14, 2020.
    27 changes: 27 additions & 0 deletions get_max_value.ts
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,27 @@
    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 < n) {
    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])