Problème du Sac à  Dos fraction

#include <stdio.h>
#include <stdlib.h>

// Structure pour représenter un article
typedef struct {
    int valeur;
    int poids;
    float rapport;
} Article;

// Fonction de comparaison pour le tri décroissant selon le rapport
int comparer(const void* a, const void* b) {
    Article* articleA = (Article*)a;
    Article* articleB = (Article*)b;
    
    if (articleA->rapport < articleB->rapport)
        return 1;
    else if (articleA->rapport > articleB->rapport)
        return -1;
    else
        return 0;
}

float sacADos(Article articles[], int n, int capacite) {
    // Calculer les rapports valeur/poids
    for (int i = 0; i < n; i++) {
        articles[i].rapport = (float)articles[i].valeur / articles[i].poids;
    }
    
    // Trier les articles par rapport décroissant
    qsort(articles, n, sizeof(Article), comparer);
    
    float valeurTotale = 0.0;
    int poidsRestant = capacite;
    
    printf("Articles sélectionnés (dans l'ordre) :\n");
    
    for (int i = 0; i < n; i++) {
        if (articles[i].poids <= poidsRestant) {
            // Prendre l'article entier
            printf("  - Article entier (valeur=%d, poids=%d, rapport=%.2f)\n", 
                   articles[i].valeur, articles[i].poids, articles[i].rapport);
            poidsRestant -= articles[i].poids;
            valeurTotale += articles[i].valeur;
        } else {
            // Prendre une fraction de l'article
            float fraction = (float)poidsRestant / articles[i].poids;
            printf("  - Fraction de l'article (%.2f × %d = %.2f, rapport=%.2f)\n", 
                   fraction, articles[i].valeur, fraction * articles[i].valeur, articles[i].rapport);
            valeurTotale += articles[i].valeur * fraction;
            break; // Sac plein
        }
    }
    
    return valeurTotale;
}

int main() {
    // Exemple 1
    Article articles1[] = {
        {60, 10, 0},
        {100, 20, 0},
        {100, 60, 0},
        {40, 20, 0}
    };
    int n1 = sizeof(articles1) / sizeof(articles1[0]);
    int capacite1 = 50;
    
    printf("=== Exemple 1 ===\n");
    printf("Articles : (60,10), (100,20), (100,60), (40,20)\n");
    printf("Capacité : %d\n\n", capacite1);
    
    float resultat1 = sacADos(articles1, n1, capacite1);
    printf("\nValeur maximale dans le sac à dos = %.2f\n\n", resultat1);
    
    // Exemple 2
    Article articles2[] = {
        {60, 10, 0},
        {100, 20, 0},
        {120, 30, 0}
    };
    int n2 = sizeof(articles2) / sizeof(articles2[0]);
    int capacite2 = 50;
    
    printf("=== Exemple 2 ===\n");
    printf("Articles : (60,10), (100,20), (120,30)\n");
    printf("Capacité : %d\n\n", capacite2);
    
    float resultat2 = sacADos(articles2, n2, capacite2);
    printf("\nValeur maximale dans le sac à dos = %.2f\n\n", resultat2);
    
    // Exemple 3 (cas d'un seul article)
    Article articles3[] = {
        {500, 30, 0}
    };
    int n3 = sizeof(articles3) / sizeof(articles3[0]);
    int capacite3 = 20;
    
    printf("=== Exemple 3 ===\n");
    printf("Articles : (500,30)\n");
    printf("Capacité : %d\n\n", capacite3);
    
    float resultat3 = sacADos(articles3, n3, capacite3);
    printf("\nValeur maximale dans le sac à dos = %.2f\n", resultat3);
    
    return 0;
}

def sac_dos_fractionnaire(articles, capacite):
    """
    Résout le problème du sac à dos fractionnaire.
    
    Paramètres:
    articles: liste de tuples (valeur, poids)
    capacite: capacité maximale du sac
    
    Retourne:
    float: valeur totale maximale
    """
    # Créer une liste d'articles avec leur rapport valeur/poids
    articles_avec_rapport = []
    for i, (valeur, poids) in enumerate(articles):
        rapport = valeur / poids
        articles_avec_rapport.append((valeur, poids, rapport, i))
    
    # Trier par rapport décroissant
    articles_avec_rapport.sort(key=lambda x: x[2], reverse=True)
    
    valeur_totale = 0.0
    poids_restant = capacite
    selection = []  # Pour stocker les articles sélectionnés
    
    for valeur, poids, rapport, index in articles_avec_rapport:
        if poids <= poids_restant:
            # Prendre l'article entier
            selection.append((index, 1.0, valeur, poids))
            poids_restant -= poids
            valeur_totale += valeur
        else:
            # Prendre une fraction de l'article
            fraction = poids_restant / poids
            selection.append((index, fraction, valeur * fraction, poids_restant))
            valeur_totale += valeur * fraction
            break  # Sac plein
    
    # Afficher les détails de la sélection
    print("Articles sélectionnés :")
    for index, fraction, valeur_contrib, poids_contrib in selection:
        article_original = articles[index]
        if fraction == 1.0:
            print(f"  - Article {index+1}: entier (valeur={article_original[0]}, poids={article_original[1]})")
        else:
            print(f"  - Article {index+1}: fraction {fraction:.2f} (valeur={article_original[0]} × {fraction:.2f} = {valeur_contrib:.2f}, poids={poids_contrib:.1f})")
    
    return valeur_totale

def afficher_resultat(articles, capacite):
    """Affiche le résultat de façon détaillée"""
    print(f"Articles : {articles}")
    print(f"Capacité : {capacite}")
    print()
    
    resultat = sac_dos_fractionnaire(articles, capacite)
    print(f"\nValeur maximale dans le sac à dos = {resultat:.2f}")
    print("-" * 50)

# Tester la fonction avec les exemples
print("=== Exemple 1 ===")
articles1 = [(60, 10), (100, 20), (100, 60), (40, 20)]
afficher_resultat(articles1, 50)

print("\n=== Exemple 2 ===")
articles2 = [(60, 10), (100, 20), (120, 30)]
afficher_resultat(articles2, 50)

print("\n=== Exemple 3 ===")
articles3 = [(500, 30)]
afficher_resultat(articles3, 20)

print("\n=== Exemple 4 (test interactif) ===")
# Test avec des valeurs personnalisées
articles_test = [(90, 20), (120, 30), (60, 10), (200, 40)]
capacite_test = 60
afficher_resultat(articles_test, capacite_test)