def min_coins(coins, amount):
    coins = sorted(coins, reverse=True)       # largest denomination first
    picked = []
    for x in coins:
        k = amount // x                       # as many of this coin as still fit
        picked.extend([x] * k)
        amount -= k * x
        if amount == 0:
            break
    return picked

for amount in (52, 93):
    picked = min_coins([10, 5, 2, 1], amount)
    print(f"{amount} → {len(picked)} coins: {' '.join(map(str, picked))}")

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> minCoins(vector<int> coins, int amount) {
    sort(coins.rbegin(), coins.rend());            // largest denomination first
    vector<int> picked;
    for (int x : coins) {
        int k = amount / x;                        // as many of this coin as still fit
        for (int j = 0; j < k; j++) picked.push_back(x);
        amount -= k * x;
        if (amount == 0) break;
    }
    return picked;
}

int main() {
    for (int amount : {52, 93}) {
        vector<int> picked = minCoins({10, 5, 2, 1}, amount);
        cout << amount << " → " << picked.size() << " coins:";
        for (int c : picked) cout << " " << c;
        cout << "\n";
    }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static List<Integer> minCoins(int[] coins, int amount) {
        int[] c = coins.clone();
        Arrays.sort(c);                                   // ascending …
        List<Integer> picked = new ArrayList<>();
        for (int i = c.length - 1; i >= 0; i--) {         // … so walk it backwards: largest first
            int k = amount / c[i];                        // as many of this coin as still fit
            for (int j = 0; j < k; j++) picked.add(c[i]);
            amount -= k * c[i];
            if (amount == 0) break;
        }
        return picked;
    }

    public static void main(String[] args) {
        for (int amount : new int[]{52, 93}) {
            List<Integer> picked = minCoins(new int[]{10, 5, 2, 1}, amount);
            StringBuilder sb = new StringBuilder();
            for (int x : picked) sb.append(' ').append(x);
            System.out.println(amount + " → " + picked.size() + " coins:" + sb);
        }
    }
}

function minCoins(coins, amount) {
    const sorted = [...coins].sort((a, b) => b - a);   // largest denomination first
    const picked = [];
    for (const x of sorted) {
        const k = Math.floor(amount / x);               // as many of this coin as still fit
        for (let j = 0; j < k; j++) picked.push(x);
        amount -= k * x;
        if (amount === 0) break;
    }
    return picked;
}

for (const amount of [52, 93]) {
    const picked = minCoins([10, 5, 2, 1], amount);
    console.log(`${amount} → ${picked.length} coins: ${picked.join(" ")}`);
}

52 → 6 coins: 10 10 10 10 10 2
93 → 11 coins: 10 10 10 10 10 10 10 10 10 2 1

getOptimal(items):
    res = empty solution
    while not all items considered:
        i = selectBestItem()          # the greedy choice (largest coin, earliest finish, …)
        if feasible(res + i):         # does adding i still respect the constraints?
            res = res + i
    return res

def greedy(coins, amount):
    count = 0
    for x in sorted(coins, reverse=True):
        count += amount // x
        amount %= x
    return count

def optimal(coins, amount):                     # dynamic programming — always correct
    best = [0] + [float("inf")] * amount
    for a in range(1, amount + 1):
        for x in coins:
            if x <= a:
                best[a] = min(best[a], best[a - x] + 1)
    return best[amount]

print("greedy :", greedy([18, 1, 10], 20))     # 18 + 1 + 1
print("optimal:", optimal([18, 1, 10], 20))    # 10 + 10

greedy : 3
optimal: 2

time  1   2   3   4   5   6   7   8   9   10
(2,3)     ├───┤                                ✔ chosen (ends first)
(1,4) ├───────────┤                            ✘ starts at 1 < 3
(5,8)                 ├───────────┤            ✔ chosen (5 ≥ 3)
(6,10)                    ├───────────────┤    ✘ starts at 6 < 8

def max_activities(activities):
    activities = sorted(activities, key=lambda a: a[1])   # earliest finish first
    chosen = [activities[0]]
    for start, finish in activities[1:]:
        if start >= chosen[-1][1]:                        # no overlap with the last chosen one
            chosen.append((start, finish))
    return chosen

acts = [(2, 3), (1, 4), (5, 8), (6, 10)]
chosen = max_activities(acts)
print("selected:", " ".join(f"({s},{f})" for s, f in chosen))
print("count:", len(chosen))

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int,int>> maxActivities(vector<pair<int,int>> acts) {
    sort(acts.begin(), acts.end(),
         [](const pair<int,int>& a, const pair<int,int>& b) { return a.second < b.second; });  // earliest finish first
    vector<pair<int,int>> chosen = {acts[0]};
    for (size_t i = 1; i < acts.size(); i++)
        if (acts[i].first >= chosen.back().second)         // no overlap with the last chosen one
            chosen.push_back(acts[i]);
    return chosen;
}

int main() {
    vector<pair<int,int>> acts = {{2, 3}, {1, 4}, {5, 8}, {6, 10}};
    vector<pair<int,int>> chosen = maxActivities(acts);
    cout << "selected:";
    for (auto& [s, f] : chosen) cout << " (" << s << "," << f << ")";
    cout << "\ncount: " << chosen.size() << "\n";
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static List<int[]> maxActivities(int[][] acts) {
        Arrays.sort(acts, (a, b) -> a[1] - b[1]);             // earliest finish first
        List<int[]> chosen = new ArrayList<>();
        chosen.add(acts[0]);
        for (int i = 1; i < acts.length; i++)
            if (acts[i][0] >= chosen.get(chosen.size() - 1)[1])   // no overlap with the last chosen one
                chosen.add(acts[i]);
        return chosen;
    }

    public static void main(String[] args) {
        int[][] acts = {{2, 3}, {1, 4}, {5, 8}, {6, 10}};
        List<int[]> chosen = maxActivities(acts);
        StringBuilder sb = new StringBuilder("selected:");
        for (int[] a : chosen) sb.append(" (").append(a[0]).append(",").append(a[1]).append(")");
        System.out.println(sb);
        System.out.println("count: " + chosen.size());
    }
}

function maxActivities(activities) {
    const acts = [...activities].sort((a, b) => a[1] - b[1]);   // earliest finish first
    const chosen = [acts[0]];
    for (let i = 1; i < acts.length; i++)
        if (acts[i][0] >= chosen[chosen.length - 1][1])          // no overlap with the last chosen one
            chosen.push(acts[i]);
    return chosen;
}

const acts = [[2, 3], [1, 4], [5, 8], [6, 10]];
const chosen = maxActivities(acts);
console.log("selected:", chosen.map(([s, f]) => `(${s},${f})`).join(" "));
console.log("count:", chosen.length);

selected: (2,3) (5,8)
count: 2

def fractional_knapsack(items, capacity):
    items = sorted(items, key=lambda it: it[1] / it[0], reverse=True)   # best value per kg first
    total = 0.0
    for w, v in items:
        if capacity == 0:
            break
        if w <= capacity:                             # the whole item fits
            capacity -= w
            total += v
            print(f"item w={w} v={v}: take all → {v:.2f}")
        else:                                         # only a fraction fits — fill up and stop
            part = v * capacity / w
            print(f"item w={w} v={v}: take {capacity}/{w} → {part:.2f}")
            total += part
            capacity = 0
    return total

items = [(50, 600), (20, 500), (30, 400)]             # (weight, value)
print(f"max value: {fractional_knapsack(items, 70):.2f}")

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;

struct Item { int weight, value; };

double fractionalKnapsack(vector<Item> items, int capacity) {
    sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return (double)a.value / a.weight > (double)b.value / b.weight;   // best value per kg first
    });
    double total = 0;
    for (const Item& it : items) {
        if (capacity == 0) break;
        if (it.weight <= capacity) {                   // the whole item fits
            capacity -= it.weight;
            total += it.value;
            cout << "item w=" << it.weight << " v=" << it.value << ": take all → " << (double)it.value << "\n";
        } else {                                       // only a fraction fits — fill up and stop
            double part = (double)it.value * capacity / it.weight;
            cout << "item w=" << it.weight << " v=" << it.value << ": take " << capacity << "/" << it.weight
                 << " → " << part << "\n";
            total += part;
            capacity = 0;
        }
    }
    return total;
}

int main() {
    cout << fixed << setprecision(2);
    vector<Item> items = {{50, 600}, {20, 500}, {30, 400}};   // {weight, value}
    double best = fractionalKnapsack(items, 70);               // run first — it prints the steps
    cout << "max value: " << best << "\n";
}

import java.util.Arrays;
import java.util.Locale;

public class Main {
    static double fractionalKnapsack(int[][] items, int capacity) {
        Arrays.sort(items, (a, b) -> Double.compare((double) b[1] / b[0], (double) a[1] / a[0]));  // best ratio first
        double total = 0;
        for (int[] it : items) {
            int w = it[0], v = it[1];
            if (capacity == 0) break;
            if (w <= capacity) {                           // the whole item fits
                capacity -= w;
                total += v;
                System.out.println("item w=" + w + " v=" + v + ": take all → " + String.format(Locale.US, "%.2f", (double) v));
            } else {                                       // only a fraction fits — fill up and stop
                double part = (double) v * capacity / w;
                System.out.println("item w=" + w + " v=" + v + ": take " + capacity + "/" + w + " → "
                                   + String.format(Locale.US, "%.2f", part));
                total += part;
                capacity = 0;
            }
        }
        return total;
    }

    public static void main(String[] args) {
        int[][] items = {{50, 600}, {20, 500}, {30, 400}};   // {weight, value}
        double best = fractionalKnapsack(items, 70);           // run first — it prints the steps
        System.out.println(String.format(Locale.US, "max value: %.2f", best));
    }
}

function fractionalKnapsack(items, capacity) {
    const sorted = [...items].sort((a, b) => b[1] / b[0] - a[1] / a[0]);   // best value per kg first
    let total = 0;
    for (const [w, v] of sorted) {
        if (capacity === 0) break;
        if (w <= capacity) {                               // the whole item fits
            capacity -= w;
            total += v;
            console.log(`item w=${w} v=${v}: take all → ${v.toFixed(2)}`);
        } else {                                           // only a fraction fits — fill up and stop
            const part = v * capacity / w;
            console.log(`item w=${w} v=${v}: take ${capacity}/${w} → ${part.toFixed(2)}`);
            total += part;
            capacity = 0;
        }
    }
    return total;
}

const items = [[50, 600], [20, 500], [30, 400]];         // [weight, value]
console.log(`max value: ${fractionalKnapsack(items, 70).toFixed(2)}`);

item w=20 v=500: take all → 500.00
item w=30 v=400: take all → 400.00
item w=50 v=600: take 20/50 → 240.00
max value: 1140.00

def job_sequencing(jobs, slots):
    jobs = sorted(jobs, key=lambda j: j[2], reverse=True)   # most profitable first
    schedule = [None] * slots                               # schedule[s] = job running in slot s+1
    for name, deadline, profit in jobs:
        for s in range(min(slots, deadline) - 1, -1, -1):  # latest free slot before the deadline
            if schedule[s] is None:
                schedule[s] = (name, profit)
                break
    return schedule

jobs = [("a", 2, 100), ("b", 1, 19), ("c", 2, 27), ("d", 1, 25), ("e", 3, 15)]   # (name, deadline, profit)
total = 0
for s, job in enumerate(job_sequencing(jobs, 3)):
    if job is not None:
        print(f"slot {s + 1}: {job[0]} (profit {job[1]})")
        total += job[1]
print("total profit:", total)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Job { string name; int deadline, profit; };

vector<Job> jobSequencing(vector<Job> jobs, int slots) {
    sort(jobs.begin(), jobs.end(),
         [](const Job& a, const Job& b) { return a.profit > b.profit; });   // most profitable first
    vector<Job> schedule(slots, Job{"", 0, 0});                // schedule[s] = job running in slot s+1
    for (const Job& j : jobs)
        for (int s = min(slots, j.deadline) - 1; s >= 0; s--)  // latest free slot before the deadline
            if (schedule[s].name.empty()) { schedule[s] = j; break; }
    return schedule;
}

int main() {
    vector<Job> jobs = {{"a", 2, 100}, {"b", 1, 19}, {"c", 2, 27}, {"d", 1, 25}, {"e", 3, 15}};
    vector<Job> schedule = jobSequencing(jobs, 3);
    int total = 0;
    for (int s = 0; s < (int)schedule.size(); s++) {
        if (schedule[s].name.empty()) continue;
        cout << "slot " << s + 1 << ": " << schedule[s].name << " (profit " << schedule[s].profit << ")\n";
        total += schedule[s].profit;
    }
    cout << "total profit: " << total << "\n";
}

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class Job {
        String name; int deadline, profit;
        Job(String n, int d, int p) { name = n; deadline = d; profit = p; }
    }

    static Job[] jobSequencing(List<Job> jobs, int slots) {
        jobs.sort((a, b) -> b.profit - a.profit);               // most profitable first
        Job[] schedule = new Job[slots];                         // schedule[s] = job running in slot s+1
        for (Job j : jobs)
            for (int s = Math.min(slots, j.deadline) - 1; s >= 0; s--)   // latest free slot before the deadline
                if (schedule[s] == null) { schedule[s] = j; break; }
        return schedule;
    }

    public static void main(String[] args) {
        List<Job> jobs = new ArrayList<>(List.of(new Job("a", 2, 100), new Job("b", 1, 19),
                new Job("c", 2, 27), new Job("d", 1, 25), new Job("e", 3, 15)));
        Job[] schedule = jobSequencing(jobs, 3);
        int total = 0;
        for (int s = 0; s < schedule.length; s++) {
            if (schedule[s] == null) continue;
            System.out.println("slot " + (s + 1) + ": " + schedule[s].name + " (profit " + schedule[s].profit + ")");
            total += schedule[s].profit;
        }
        System.out.println("total profit: " + total);
    }
}

function jobSequencing(jobs, slots) {
    const sorted = [...jobs].sort((a, b) => b.profit - a.profit);   // most profitable first
    const schedule = new Array(slots).fill(null);                   // schedule[s] = job running in slot s+1
    for (const job of sorted)
        for (let s = Math.min(slots, job.deadline) - 1; s >= 0; s--)   // latest free slot before the deadline
            if (schedule[s] === null) { schedule[s] = job; break; }
    return schedule;
}

const jobs = [
    { name: "a", deadline: 2, profit: 100 }, { name: "b", deadline: 1, profit: 19 },
    { name: "c", deadline: 2, profit: 27 },  { name: "d", deadline: 1, profit: 25 },
    { name: "e", deadline: 3, profit: 15 },
];
let total = 0;
jobSequencing(jobs, 3).forEach((job, s) => {
    if (job === null) return;
    console.log(`slot ${s + 1}: ${job.name} (profit ${job.profit})`);
    total += job.profit;
});
console.log("total profit:", total);

slot 1: c (profit 27)
slot 2: a (profit 100)
slot 3: e (profit 15)
total profit: 142

step 1  heap: c:10  b:20  a:70        pop c, b → new node $:30
step 2  heap: $:30  a:70              pop $, a → new node $:100
step 3  heap: $:100                   one node left — the root

           ($:100)
          0/     \1
      ($:30)      a:70   → a = 1
     0/    \1
   c:10    b:20          → c = 00, b = 01

import heapq

class Node:
    def __init__(self, ch, freq, left=None, right=None):
        self.ch, self.freq, self.left, self.right = ch, freq, left, right

def build_huffman_tree(freq):
    heap, order = [], 0
    for ch, f in freq:                                      # (freq, insertion order, node) — order breaks ties
        heap.append((f, order, Node(ch, f)))
        order += 1
    heapq.heapify(heap)
    while len(heap) > 1:
        f1, _, left = heapq.heappop(heap)                   # the two least frequent nodes …
        f2, _, right = heapq.heappop(heap)
        heapq.heappush(heap, (f1 + f2, order, Node('$', f1 + f2, left, right)))   # … become siblings
        order += 1
    return heap[0][2]

def print_codes(node, code, codes):
    if node.ch != '$':                                      # leaf = an input character
        print(f"{node.ch}: {code}")
        codes[node.ch] = code
        return
    print_codes(node.left, code + "0", codes)
    print_codes(node.right, code + "1", codes)

freq = [('a', 70), ('b', 20), ('c', 10)]
root = build_huffman_tree(freq)
codes = {}
print_codes(root, "", codes)
total = sum(f * len(codes[ch]) for ch, f in freq)
chars = sum(f for _, f in freq)
print(f"total bits: {total} (fixed-length 2-bit codes: {2 * chars})")

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <map>
using namespace std;

struct Node {
    char ch; int freq; Node *left, *right;
    Node(char c, int f, Node* l = nullptr, Node* r = nullptr) : ch(c), freq(f), left(l), right(r) {}
};
struct Entry { int freq, order; Node* node; };
struct ByFreq {                                             // min-heap on (freq, insertion order)
    bool operator()(const Entry& a, const Entry& b) const {
        return a.freq != b.freq ? a.freq > b.freq : a.order > b.order;
    }
};

Node* buildHuffmanTree(const vector<pair<char,int>>& freq) {
    priority_queue<Entry, vector<Entry>, ByFreq> heap;
    int order = 0;
    for (auto& [ch, f] : freq) heap.push({f, order++, new Node(ch, f)});
    while (heap.size() > 1) {
        Entry l = heap.top(); heap.pop();                   // the two least frequent nodes …
        Entry r = heap.top(); heap.pop();
        heap.push({l.freq + r.freq, order++, new Node('$', l.freq + r.freq, l.node, r.node)});  // … become siblings
    }
    return heap.top().node;
}

void printCodes(Node* n, const string& code, map<char,string>& codes) {
    if (n->ch != '$') {                                     // leaf = an input character
        cout << n->ch << ": " << code << "\n";
        codes[n->ch] = code;
        return;
    }
    printCodes(n->left, code + "0", codes);
    printCodes(n->right, code + "1", codes);
}

int main() {
    vector<pair<char,int>> freq = {{'a', 70}, {'b', 20}, {'c', 10}};
    Node* root = buildHuffmanTree(freq);
    map<char,string> codes;
    printCodes(root, "", codes);
    int total = 0, chars = 0;
    for (auto& [ch, f] : freq) { total += f * (int)codes[ch].size(); chars += f; }
    cout << "total bits: " << total << " (fixed-length 2-bit codes: " << 2 * chars << ")\n";
}

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Main {
    static class Node {
        char ch; int freq, order; Node left, right;
        Node(char c, int f, int o, Node l, Node r) { ch = c; freq = f; order = o; left = l; right = r; }
    }

    static Node buildHuffmanTree(char[] chars, int[] freqs) {
        PriorityQueue<Node> heap = new PriorityQueue<>((a, b) ->
                a.freq != b.freq ? a.freq - b.freq : a.order - b.order);   // min-heap on (freq, insertion order)
        int order = 0;
        for (int i = 0; i < chars.length; i++) heap.add(new Node(chars[i], freqs[i], order++, null, null));
        while (heap.size() > 1) {
            Node left = heap.poll();                                     // the two least frequent nodes …
            Node right = heap.poll();
            heap.add(new Node('$', left.freq + right.freq, order++, left, right));   // … become siblings
        }
        return heap.poll();
    }

    static void printCodes(Node n, String code, Map<Character, String> codes) {
        if (n.ch != '$') {                                               // leaf = an input character
            System.out.println(n.ch + ": " + code);
            codes.put(n.ch, code);
            return;
        }
        printCodes(n.left, code + "0", codes);
        printCodes(n.right, code + "1", codes);
    }

    public static void main(String[] args) {
        char[] chars = {'a', 'b', 'c'};
        int[] freqs = {70, 20, 10};
        Node root = buildHuffmanTree(chars, freqs);
        Map<Character, String> codes = new HashMap<>();
        printCodes(root, "", codes);
        int total = 0, count = 0;
        for (int i = 0; i < chars.length; i++) { total += freqs[i] * codes.get(chars[i]).length(); count += freqs[i]; }
        System.out.println("total bits: " + total + " (fixed-length 2-bit codes: " + 2 * count + ")");
    }
}

class Node {
    constructor(ch, freq, order, left = null, right = null) {
        Object.assign(this, { ch, freq, order, left, right });
    }
}

class MinHeap {                               // keyed on (freq, insertion order) so ties are deterministic
    constructor() { this.a = []; }
    less(i, j) { const x = this.a[i], y = this.a[j]; return x.freq !== y.freq ? x.freq < y.freq : x.order < y.order; }
    swap(i, j) { [this.a[i], this.a[j]] = [this.a[j], this.a[i]]; }
    push(node) {
        this.a.push(node);
        for (let i = this.a.length - 1; i > 0 && this.less(i, (i - 1) >> 1); i = (i - 1) >> 1) this.swap(i, (i - 1) >> 1);
    }
    pop() {
        const top = this.a[0], last = this.a.pop();
        if (this.a.length) {
            this.a[0] = last;
            for (let i = 0;;) {
                let m = i; const l = 2 * i + 1, r = l + 1;
                if (l < this.a.length && this.less(l, m)) m = l;
                if (r < this.a.length && this.less(r, m)) m = r;
                if (m === i) break;
                this.swap(i, m); i = m;
            }
        }
        return top;
    }
    get size() { return this.a.length; }
}

function buildHuffmanTree(freq) {
    const heap = new MinHeap();
    let order = 0;
    for (const [ch, f] of freq) heap.push(new Node(ch, f, order++));
    while (heap.size > 1) {
        const left = heap.pop();                                  // the two least frequent nodes …
        const right = heap.pop();
        heap.push(new Node('$', left.freq + right.freq, order++, left, right));   // … become siblings
    }
    return heap.pop();
}

function printCodes(n, code, codes) {
    if (n.ch !== '$') { console.log(`${n.ch}: ${code}`); codes[n.ch] = code; return; }   // leaf
    printCodes(n.left, code + "0", codes);
    printCodes(n.right, code + "1", codes);
}

const freq = [['a', 70], ['b', 20], ['c', 10]];
const codes = {};
printCodes(buildHuffmanTree(freq), "", codes);
const total = freq.reduce((s, [ch, f]) => s + f * codes[ch].length, 0);
const chars = freq.reduce((s, [, f]) => s + f, 0);
console.log(`total bits: ${total} (fixed-length 2-bit codes: ${2 * chars})`);

c: 00
b: 01
a: 1
total bits: 130 (fixed-length 2-bit codes: 200)