Açgözlü (Greedy) Algoritmalar

package main

import (
	"fmt"
	"slices"
)

type Activity struct {
	Name       string
	Start, End int
}

// selectByEarliestEnd: DOĞRU açgözlü strateji
func selectByEarliestEnd(activities []Activity) []Activity {
	sorted := slices.Clone(activities)
	slices.SortFunc(sorted, func(a, b Activity) int {
		if a.End != b.End {
			return a.End - b.End
		}
		return a.Start - b.Start
	})

	var chosen []Activity
	lastEnd := -1 << 62
	for _, a := range sorted {
		if a.Start >= lastEnd {
			chosen = append(chosen, a)
			lastEnd = a.End
		}
	}
	return chosen
}

// selectByEarliestStart: YANLIŞ strateji — uzun bir etkinlik her şeyi engeller
func selectByEarliestStart(activities []Activity) []Activity {
	sorted := slices.Clone(activities)
	slices.SortFunc(sorted, func(a, b Activity) int { return a.Start - b.Start })

	var chosen []Activity
	lastEnd := -1 << 62
	for _, a := range sorted {
		if a.Start >= lastEnd {
			chosen = append(chosen, a)
			lastEnd = a.End
		}
	}
	return chosen
}

// selectByShortest: YANLIŞ strateji — kısa bir etkinlik iki uzunu engelleyebilir
func selectByShortest(activities []Activity) []Activity {
	sorted := slices.Clone(activities)
	slices.SortFunc(sorted, func(a, b Activity) int {
		return (a.End - a.Start) - (b.End - b.Start)
	})

	var chosen []Activity
	for _, a := range sorted {
		fits := true
		for _, c := range chosen {
			if a.Start < c.End && c.Start < a.End {
				fits = false
				break
			}
		}
		if fits {
			chosen = append(chosen, a)
		}
	}
	slices.SortFunc(chosen, func(a, b Activity) int { return a.Start - b.Start })
	return chosen
}

func names(as []Activity) []string {
	out := make([]string, len(as))
	for i, a := range as {
		out[i] = fmt.Sprintf("%s[%d-%d]", a.Name, a.Start, a.End)
	}
	return out
}

func main() {
	activities := []Activity{
		{"A", 1, 4}, {"B", 3, 5}, {"C", 0, 6}, {"D", 5, 7}, {"E", 3, 9},
		{"F", 5, 9}, {"G", 6, 10}, {"H", 8, 11}, {"I", 8, 12}, {"J", 2, 14}, {"K", 12, 16},
	}

	best := selectByEarliestEnd(activities)
	fmt.Println("en erken biten (DOĞRU):", names(best))
	fmt.Println("  seçilen sayı:", len(best))

	fmt.Println()
	byStart := selectByEarliestStart(activities)
	fmt.Println("en erken başlayan (yanlış):", names(byStart))
	fmt.Println("  seçilen sayı:", len(byStart))

	fmt.Println()
	byShort := selectByShortest(activities)
	fmt.Println("en kısa süreli (yanlış):", names(byShort))
	fmt.Println("  seçilen sayı:", len(byShort))

	// En kısa stratejisinin açıkça başarısız olduğu örnek
	fmt.Println()
	counter := []Activity{
		{"uzun1", 0, 10}, {"kısa", 9, 11}, {"uzun2", 10, 20},
	}
	fmt.Println("karşı örnek:", names(counter))
	fmt.Println("  en kısa ile:", names(selectByShortest(counter)), "→", len(selectByShortest(counter)), "etkinlik")
	fmt.Println("  en erken biten ile:", names(selectByEarliestEnd(counter)), "→", len(selectByEarliestEnd(counter)), "etkinlik")
}

package main

import (
	"fmt"
	"slices"
)

// greedyCoins: en büyükten başlar — HER PARA SİSTEMİNDE DOĞRU DEĞİL
func greedyCoins(coins []int, amount int) ([]int, bool) {
	sorted := slices.Clone(coins)
	slices.Sort(sorted)
	slices.Reverse(sorted)

	var used []int
	for _, c := range sorted {
		for amount >= c {
			used = append(used, c)
			amount -= c
		}
	}
	return used, amount == 0
}

// optimalCoins: dinamik programlama — her zaman en iyi sonucu verir
func optimalCoins(coins []int, amount int) ([]int, bool) {
	const inf = 1 << 30
	best := make([]int, amount+1)
	choice := make([]int, amount+1)
	for i := 1; i <= amount; i++ {
		best[i] = inf
	}

	for i := 1; i <= amount; i++ {
		for _, c := range coins {
			if c <= i && best[i-c]+1 < best[i] {
				best[i] = best[i-c] + 1
				choice[i] = c
			}
		}
	}
	if best[amount] >= inf {
		return nil, false
	}

	var used []int
	for amount > 0 {
		used = append(used, choice[amount])
		amount -= choice[amount]
	}
	slices.Sort(used)
	slices.Reverse(used)
	return used, true
}

func main() {
	systems := []struct {
		name   string
		coins  []int
		amount int
	}{
		{"Türk lirası kuruşları", []int{1, 5, 10, 25, 50}, 87},
		{"kanonik olmayan sistem", []int{1, 15, 25}, 30},
		{"kanonik olmayan 2", []int{1, 3, 4}, 6},
		{"eksik sistem", []int{3, 5}, 7},
	}

	for _, s := range systems {
		g, gok := greedyCoins(s.coins, s.amount)
		o, ook := optimalCoins(s.coins, s.amount)

		fmt.Printf("%s — paralar %v, tutar %d\n", s.name, s.coins, s.amount)
		if !gok {
			fmt.Println("  açgözlü: çözüm bulamadı")
		} else {
			fmt.Printf("  açgözlü: %v → %d para\n", g, len(g))
		}
		if !ook {
			fmt.Println("  en iyi:  çözüm yok")
		} else {
			fmt.Printf("  en iyi:  %v → %d para\n", o, len(o))
		}
		if gok && ook {
			fmt.Printf("  açgözlü optimal mi: %t\n", len(g) == len(o))
		}
		fmt.Println()
	}

	fmt.Println("Sonuç: açgözlü yaklaşım yalnızca 'kanonik' para sistemlerinde doğrudur.")
	fmt.Println("Gerçek para birimleri kanoniktir (bilinçli tasarım); rastgele sistemler değil.")
}

package main

import (
	"fmt"
	"slices"
)

type Item struct {
	Name   string
	Value  float64
	Weight float64
}

type Taken struct {
	Item     Item
	Fraction float64
}

// fractionalKnapsack: açgözlü OPTIMAL — eşyalar bölünebilir
func fractionalKnapsack(items []Item, capacity float64) ([]Taken, float64) {
	sorted := slices.Clone(items)
	// Birim değere göre azalan sırala
	slices.SortFunc(sorted, func(a, b Item) int {
		ra, rb := a.Value/a.Weight, b.Value/b.Weight
		switch {
		case ra > rb:
			return -1
		case ra < rb:
			return 1
		}
		return 0
	})

	var taken []Taken
	total := 0.0
	remaining := capacity

	for _, it := range sorted {
		if remaining <= 0 {
			break
		}
		if it.Weight <= remaining {
			taken = append(taken, Taken{it, 1.0})
			total += it.Value
			remaining -= it.Weight
			continue
		}
		// Kalan kapasiteye sığan kısmı al
		fraction := remaining / it.Weight
		taken = append(taken, Taken{it, fraction})
		total += it.Value * fraction
		remaining = 0
	}
	return taken, total
}

// integralGreedy: BÖLÜNEMEZ eşyalarda açgözlü — optimal DEĞİL
func integralGreedy(items []Item, capacity float64) ([]Item, float64) {
	sorted := slices.Clone(items)
	slices.SortFunc(sorted, func(a, b Item) int {
		ra, rb := a.Value/a.Weight, b.Value/b.Weight
		switch {
		case ra > rb:
			return -1
		case ra < rb:
			return 1
		}
		return 0
	})

	var taken []Item
	total, remaining := 0.0, capacity
	for _, it := range sorted {
		if it.Weight <= remaining {
			taken = append(taken, it)
			total += it.Value
			remaining -= it.Weight
		}
	}
	return taken, total
}

// integralOptimal: kaba kuvvetle tüm alt kümeleri dene
func integralOptimal(items []Item, capacity float64) ([]Item, float64) {
	n := len(items)
	bestValue := 0.0
	var bestSet []Item

	for mask := range 1 << n {
		weight, value := 0.0, 0.0
		var set []Item
		for i := range n {
			if mask&(1<<i) != 0 {
				weight += items[i].Weight
				value += items[i].Value
				set = append(set, items[i])
			}
		}
		if weight <= capacity && value > bestValue {
			bestValue, bestSet = value, set
		}
	}
	return bestSet, bestValue
}

func main() {
	items := []Item{
		{"altın", 60, 10},
		{"gümüş", 100, 20},
		{"bronz", 120, 30},
	}
	const capacity = 50

	fmt.Println("eşyalar (değer/ağırlık oranı):")
	for _, it := range items {
		fmt.Printf("  %-8s değer=%-6.0f ağırlık=%-4.0f oran=%.2f\n",
			it.Name, it.Value, it.Weight, it.Value/it.Weight)
	}
	fmt.Println("kapasite:", capacity)

	taken, total := fractionalKnapsack(items, capacity)
	fmt.Println()
	fmt.Println("PARÇALI sırt çantası (açgözlü optimal):")
	for _, t := range taken {
		fmt.Printf("  %-8s %.0f%% alındı → değer %.1f\n",
			t.Item.Name, t.Fraction*100, t.Item.Value*t.Fraction)
	}
	fmt.Printf("  toplam değer: %.1f\n", total)

	// Bölünemez durumda açgözlü başarısız olabilir
	fmt.Println()
	indivisible := []Item{
		{"A", 60, 10}, {"B", 100, 20}, {"C", 120, 30},
	}
	g, gv := integralGreedy(indivisible, capacity)
	o, ov := integralOptimal(indivisible, capacity)

	fmt.Println("BÖLÜNEMEZ sırt çantası:")
	fmt.Printf("  açgözlü: %v → %.0f\n", names(g), gv)
	fmt.Printf("  en iyi:  %v → %.0f\n", names(o), ov)
	fmt.Println("  açgözlü optimal mi:", gv == ov)

	// Açgözlünün başarısız olduğu örnek
	fmt.Println()
	tricky := []Item{
		{"X", 10, 5}, {"Y", 11, 6}, {"Z", 11, 6},
	}
	g2, gv2 := integralGreedy(tricky, 11)
	o2, ov2 := integralOptimal(tricky, 11)
	fmt.Println("zorlu örnek (kapasite 11):")
	fmt.Printf("  açgözlü: %v → %.0f\n", names(g2), gv2)
	fmt.Printf("  en iyi:  %v → %.0f\n", names(o2), ov2)
	fmt.Println("  açgözlü optimal mi:", gv2 == ov2)
}

func names(items []Item) []string {
	out := make([]string, len(items))
	for i, it := range items {
		out[i] = it.Name
	}
	return out
}

package main

import (
	"container/heap"
	"fmt"
	"maps"
	"slices"
	"strings"
)

type node struct {
	char        rune
	freq        int
	left, right *node
}

func (n *node) isLeaf() bool { return n.left == nil && n.right == nil }

type nodeHeap []*node

func (h nodeHeap) Len() int { return len(h) }
func (h nodeHeap) Less(i, j int) bool {
	if h[i].freq != h[j].freq {
		return h[i].freq < h[j].freq
	}
	return h[i].char < h[j].char // eşitlikte deterministik sıra
}
func (h nodeHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *nodeHeap) Push(x any)   { *h = append(*h, x.(*node)) }
func (h *nodeHeap) Pop() any     { old := *h; n := old[len(old)-1]; *h = old[:len(old)-1]; return n }

// buildHuffman: her adımda en az frekanslı iki düğümü birleştirir
func buildHuffman(freq map[rune]int) *node {
	h := &nodeHeap{}
	for _, r := range slices.Sorted(maps.Keys(freq)) {
		*h = append(*h, &node{char: r, freq: freq[r]})
	}
	heap.Init(h)

	if h.Len() == 1 { // tek karakter özel durumu
		only := heap.Pop(h).(*node)
		return &node{freq: only.freq, left: only}
	}

	for h.Len() > 1 {
		a := heap.Pop(h).(*node)
		b := heap.Pop(h).(*node)
		merged := &node{
			freq:  a.freq + b.freq,
			left:  a,
			right: b,
			char:  min(a.char, b.char), // deterministik sıralama için
		}
		heap.Push(h, merged)
	}
	return heap.Pop(h).(*node)
}

func buildCodes(root *node) map[rune]string {
	codes := map[rune]string{}
	var walk func(*node, string)
	walk = func(n *node, prefix string) {
		if n == nil {
			return
		}
		if n.isLeaf() {
			if prefix == "" {
				prefix = "0"
			}
			codes[n.char] = prefix
			return
		}
		walk(n.left, prefix+"0")
		walk(n.right, prefix+"1")
	}
	walk(root, "")
	return codes
}

func main() {
	text := "merhaba dünya merhaba go"

	freq := map[rune]int{}
	for _, r := range text {
		freq[r]++
	}

	root := buildHuffman(freq)
	codes := buildCodes(root)

	fmt.Printf("metin: %q (%d karakter)\n\n", text, len([]rune(text)))
	fmt.Printf("%-6s %8s %10s %8s\n", "karakter", "frekans", "kod", "bit")
	totalBits := 0
	for _, r := range slices.Sorted(maps.Keys(freq)) {
		code := codes[r]
		bits := freq[r] * len(code)
		totalBits += bits
		label := string(r)
		if r == ' ' {
			label = "' '"
		}
		fmt.Printf("%-6s %8d %10s %8d\n", label, freq[r], code, bits)
	}

	runeCount := len([]rune(text))
	fixedBits := runeCount * 8 // her karaktere 8 bit
	fmt.Println()
	fmt.Println("sabit uzunluklu kodlama (8 bit/karakter):", fixedBits, "bit")
	fmt.Println("Huffman kodlaması:", totalBits, "bit")
	fmt.Printf("sıkıştırma oranı: %%%.1f\n", 100*(1-float64(totalBits)/float64(fixedBits)))

	// Kodlama ve çözme
	var encoded strings.Builder
	for _, r := range text {
		encoded.WriteString(codes[r])
	}

	var decoded strings.Builder
	cur := root
	for _, bit := range encoded.String() {
		if bit == '0' {
			cur = cur.left
		} else {
			cur = cur.right
		}
		if cur.isLeaf() {
			decoded.WriteRune(cur.char)
			cur = root
		}
	}

	fmt.Println()
	fmt.Println("kodlanmış uzunluk:", encoded.Len(), "bit")
	fmt.Printf("çözülen metin: %q\n", decoded.String())
	fmt.Println("özgün metinle aynı mı:", decoded.String() == text)
}

package main

import (
	"fmt"
	"slices"
)

type Interval struct {
	Start, End int
}

// merge: çakışan aralıkları birleştirir — O(n log n)
func merge(intervals []Interval) []Interval {
	if len(intervals) == 0 {
		return nil
	}
	sorted := slices.Clone(intervals)
	slices.SortFunc(sorted, func(a, b Interval) int {
		if a.Start != b.Start {
			return a.Start - b.Start
		}
		return a.End - b.End
	})

	out := []Interval{sorted[0]}
	for _, cur := range sorted[1:] {
		last := &out[len(out)-1]
		if cur.Start <= last.End { // çakışıyor veya değiyor
			last.End = max(last.End, cur.End)
			continue
		}
		out = append(out, cur)
	}
	return out
}

// insert: sıralı ve birleşik bir listeye yeni aralık ekler
func insert(intervals []Interval, newOne Interval) []Interval {
	var out []Interval
	i := 0

	for i < len(intervals) && intervals[i].End < newOne.Start {
		out = append(out, intervals[i])
		i++
	}
	for i < len(intervals) && intervals[i].Start <= newOne.End {
		newOne.Start = min(newOne.Start, intervals[i].Start)
		newOne.End = max(newOne.End, intervals[i].End)
		i++
	}
	out = append(out, newOne)
	return append(out, intervals[i:]...)
}

// minRooms: aynı anda en fazla kaç aralık çakışıyor (kaç oda gerekir)
func minRooms(intervals []Interval) int {
	type event struct {
		time  int
		delta int
	}
	var events []event
	for _, iv := range intervals {
		events = append(events, event{iv.Start, 1}, event{iv.End, -1})
	}
	slices.SortFunc(events, func(a, b event) int {
		if a.time != b.time {
			return a.time - b.time
		}
		return a.delta - b.delta // aynı anda biten önce sayılır
	})

	current, best := 0, 0
	for _, e := range events {
		current += e.delta
		best = max(best, current)
	}
	return best
}

func main() {
	intervals := []Interval{{1, 3}, {2, 6}, {8, 10}, {15, 18}, {17, 20}}
	fmt.Println("aralıklar:", intervals)
	fmt.Println("birleştirilmiş:", merge(intervals))

	fmt.Println()
	merged := merge(intervals)
	fmt.Println("mevcut:", merged)
	fmt.Println("[4,9] eklendi:", insert(merged, Interval{4, 9}))
	fmt.Println("[25,30] eklendi:", insert(merged, Interval{25, 30}))
	fmt.Println("[0,25] eklendi:", insert(merged, Interval{0, 25}))

	fmt.Println()
	meetings := []Interval{{9, 10}, {9, 12}, {11, 13}, {9, 11}, {14, 15}}
	fmt.Println("toplantılar:", meetings)
	fmt.Println("gereken oda sayısı:", minRooms(meetings))

	fmt.Println()
	cases := [][]Interval{
		{},
		{{1, 5}},
		{{1, 2}, {3, 4}, {5, 6}},
		{{1, 10}, {2, 3}, {4, 5}},
		{{1, 4}, {4, 5}},
	}
	for _, c := range cases {
		fmt.Printf("  %-32v → %v\n", c, merge(c))
	}
}

package main

import (
	"fmt"
	"slices"
)

type Job struct {
	Name     string
	Deadline int
	Profit   int
}

// scheduleGreedy: kâra göre azalan sırala, her işi mümkün olan EN SON slota koy
func scheduleGreedy(jobs []Job) ([]string, int) {
	sorted := slices.Clone(jobs)
	slices.SortFunc(sorted, func(a, b Job) int {
		if a.Profit != b.Profit {
			return b.Profit - a.Profit
		}
		return a.Deadline - b.Deadline
	})

	maxDeadline := 0
	for _, j := range jobs {
		maxDeadline = max(maxDeadline, j.Deadline)
	}

	slots := make([]string, maxDeadline+1)
	total := 0

	for _, j := range sorted {
		// En son boş slotu bul: erken slotları başka işlere sakla
		for t := min(j.Deadline, maxDeadline); t >= 1; t-- {
			if slots[t] == "" {
				slots[t] = j.Name
				total += j.Profit
				break
			}
		}
	}

	var schedule []string
	for t := 1; t <= maxDeadline; t++ {
		if slots[t] != "" {
			schedule = append(schedule, fmt.Sprintf("t%d:%s", t, slots[t]))
		}
	}
	return schedule, total
}

// bruteForce: tüm permütasyonları dene (küçük girdiler için)
func bruteForce(jobs []Job) int {
	n := len(jobs)
	best := 0

	var try func(mask int)
	try = func(mask int) {
		// Seçilen işleri son tarihe göre sırala ve geçerli mi kontrol et
		var chosen []Job
		for i := range n {
			if mask&(1<<i) != 0 {
				chosen = append(chosen, jobs[i])
			}
		}
		slices.SortFunc(chosen, func(a, b Job) int { return a.Deadline - b.Deadline })

		profit := 0
		for i, j := range chosen {
			if i+1 > j.Deadline {
				return // geçersiz: bu iş zamanında bitmez
			}
			profit += j.Profit
		}
		best = max(best, profit)
	}

	for mask := range 1 << n {
		try(mask)
	}
	return best
}

func main() {
	jobs := []Job{
		{"A", 2, 100},
		{"B", 1, 19},
		{"C", 2, 27},
		{"D", 1, 25},
		{"E", 3, 15},
	}

	fmt.Println("işler (son tarih, kâr):")
	for _, j := range jobs {
		fmt.Printf("  %s: son tarih=%d kâr=%d\n", j.Name, j.Deadline, j.Profit)
	}

	schedule, total := scheduleGreedy(jobs)
	optimal := bruteForce(jobs)

	fmt.Println()
	fmt.Println("açgözlü program:", schedule)
	fmt.Println("açgözlü kâr:", total)
	fmt.Println("kaba kuvvet en iyi kâr:", optimal)
	fmt.Println("açgözlü optimal mi:", total == optimal)

	fmt.Println()
	fmt.Println("Bu problemde açgözlü strateji DOĞRUDUR ve değişim argümanıyla kanıtlanabilir:")
	fmt.Println("En kârlı işi mümkün olan en son slota koymak, erken slotları")
	fmt.Println("daha sıkı son tarihli işlere bırakır ve hiçbir kayba yol açmaz.")
}