그리디

/* ── 큰 동전부터 확인하며, 쓸 수 있으면 계속 사용 ──────────── */
public List<Integer> makeChange(int amount, int[] coins) {
    // coins는 반드시 큰 단위 → 작은 단위 순으로 정렬되어 있어야 함
    List<Integer> used = new ArrayList<>();
    for (int coin : coins) {
        while (amount >= coin) {
            used.add(coin);
            amount -= coin;              // 결정을 절대 되돌리지 않음
        }
    }
    return used;                     // amount가 0이 되면 끝
}

/* ── 종료 시간 기준 정렬 후, 겹치지 않으면 무조건 선택 ────── */
public List<Activity> selectActivities(List<Activity> activities) {
    activities.sort((a, b) -> a.end - b.end);   // 핵심: 종료 시간 오름차순 정렬

    List<Activity> selected = new ArrayList<>();
    int lastEnd = -1;
    for (Activity a : activities) {
        if (a.start >= lastEnd) {     // 마지막 선택과 안 겹치면
            selected.add(a);          // 무조건 선택 (되돌리지 않음)
            lastEnd = a.end;
        }
    }
    return selected;
}

/* ── "가치 높은 순"으로 그리디하게 담으면? 최적해가 아닐 수 있음 ── */
public int greedyKnapsack(int[] weights, int[] values, int capacity) {
    // 가치 기준 내림차순 정렬 후, 담을 수 있으면 무조건 담기 (그리디)
    Integer[] idx = /* 가치 내림차순으로 정렬된 인덱스라고 가정 */ null;
    int totalValue = 0;
    for (int i : idx) {
        if (weights[i] <= capacity) {
            capacity -= weights[i];
            totalValue += values[i];     // 한 번 담으면 되돌리지 않음
        }
    }
    return totalValue;                  // algo-06의 DP 결과보다 작을 수 있음!
}