Покрытие множеств

#include <stdio.h>
 Для начала будем считать что мощность множества N < 32 = sizeof(long)
 Тогда полное множество делается так:
  long U = 0;
  for(i=0; i<N; i++) U |= (1L<<i);
 Для полного перебора тоже используем шкалу
  long P = 0;
  for(i=0; i<n; i++) P |= (1L<<i);  // n - Кол-во множеств
 Пусть множества заданы числами long A[n]
 ( A[i] & (1L << j)) = 1 тогда и только, когда i-тое множество
                         содержит j-тый элемент
  double a[n]; - Веса
  double s; // цена покрытия
  long X = 0; // X содержит множества, участвующие в пробном покрытии
  long Y;  // Частичное покрытие
  while(X!=P) {
    Y = 0;
    for(i=0; i<n; i++) {
      if (Y==U) {  // Покрытие найдено
        s = 0;
        for (j=0; j<i; j++) { // Печать найденного покрытия и его цены
          if (X & (1L<<j)) {
            printf("%c ", 'A'+j);
            s += a[j];
          }
        }
        printf("s=%f\n", s);
        break;
      }
      if (X & (1L<<i)) Y = (Y | A[i]);
    }
    X++;
  }

int N=7,n=9,j,i=0;
 
// Togda polnoe mnojestvo delaetsya tak:
  long U = 0;
  for(i=0; i<7;i++ )
   {
   U |= (1L<<i);
 
    }
// Dlya polnogo perebora toje ispol'zuem shkalu
  long P = 0;
  for(i=0; i<n; i++)
  {
     P |= (1L<<i);
   }
 
 
  double a[9]; //vesa
  double s; // cena
  /// Pust' mnojestva zadany chislami long A[n]
  long A[7]={ {10100010}, {101001010}, {110011},
                 {100100100},{1010001},{1101},{10110101},};
  long X = 0; // X soderjit mnojestva, uchastvuyuschie v probnom pokrytii
  long Y;  // Chastichnoe pokrytie
  while(X!=P) {
    Y = 0;
    for(i=0; i<n; i++) {
      if (Y==U) { 
        s = 0;
        for (j=0; j<i; j++) { // Pechat' naydennogo pokrytiya i ego ceny
          if ( (X & (1L<<j))!=0 ) {
            printf("%c ", 'A'+j);
            s += a[j];
          }
        }
        printf("s=%f\n", s);
        break;
      }
      if ( (X & (1L<<i))!=0 )
       {
          Y = (Y | A[i]);
       }
    }
    X++;
  }
}

#include <stdio.h>
#include <iostream.h>
#include <string.h>
#include <conio.h>
#include <alloc.h>
void main() {
clrscr();
int N=7,n=9,j,i=0;
 
// Togda polnoe mnojestvo delaetsya tak:
  long U = 0;
  for(i=0; i<7;i++ )
   {
   U |= (1L<<i);
 
    }
// Dlya polnogo perebora toje ispol'zuem shkalu
  long P = 0;
  for(i=0; i<n; i++)
  {
     P |= (1L<<i);
   }
 
 
  double a[9]={ {1}, {3}, {2}, {2}, {1}, {2}, {3} }; //vesa
  double s; // cena
  /// Pust' mnojestva zadany chislami long A[n]
 long  A[7] = { 0xA2, 0x14A, 0x33, 0x124, 0x51, 0xD, 0xb5 };
 
  long X = 0; // X soderjit mnojestva, uchastvuyuschie v probnom pokrytii
  long Y;  // Chastichnoe pokrytie
  while(X!=P) {
    Y = 0;
    for(i=0; i<n; i++) {
      if (Y==U) {
        s = 0;
        for (j=0; j<i; j++) { // Pechat' naydennogo pokrytiya i ego ceny
          if ( (X & (1L<<j))!=0 ) {
            printf("%c ", 'A'+j);
            s += a[j];
          }
        }
        printf("s=%f\n", s);
        break;
      }
      if ( (X & (1L<<i))!=0 )
       {
          Y = (Y | A[i]);
       }
    }
    X++;
  }
}

#include <stdio.h>
// #include <iostream.h>
#include <string.h>
#include <conio.h>
// #include <alloc.h>
 
void main()
{
 int N = 7;  // kol-vo podmnogestv
 int n = 9;  // kol-vo elementov polnogo mnogestva
 int j, i;
 // double a[9]={ {1}, {3}, {2}, {2}, {1}, {2}, {3} }; // Eta stroka ne dolgna compilirovatsiy
 double a[7]={ 1, 3, 2, 2, 1, 2, 3 }; //vesa
  // Pust' mnojestva zadany chislami long A[n]
 long  A[7] = { 0xA2, 0x14A, 0x33, 0x124, 0x51, 0xD, 0xb5 };
 long U, P, X;
 long Y;  // Chastichnoe pokrytie
 double s; // cena
 
//  clrscr();
 
// Togda polnoe mnojestvo delaetsya tak:
  U = 0;
  for(i=0; i<n;i++ )   U |= (1L<<i);
// Dlya polnogo perebora toje ispol'zuem shkalu
  P = 0;
  for(i=0; i<N; i++)   P |= (1L<<i);
  X = 1; // X soderjit mnojestva, uchastvuyuschie v probnom pokrytii
  while(X!=P) {
    Y = 0;
    for(i=0; i<n; i++) {
      if (Y==U) {
        s = 0;
        for (j=0; j<i; j++) { // Pechat' naydennogo pokrytiya i ego ceny
          if ( (X & (1L<<j))!=0 ) {
            printf("%c ", 'A'+j);
            s += a[j];
          }
        }
        printf("s=%f\n", s);
        break;
      }
      if ( (X & (1L<<i))!=0 )  Y = (Y | A[i]);
    }
    X++;
  }
}

#include <stdio.h>
#include <string.h>
 
static double a[7]={ 1, 3, 2, 2, 1, 2, 3 }; //vesa
static long  A[7] = { 0xA2, 0x14A, 0x33, 0x124, 0x51, 0xD, 0xB5 };
static long U;
static int N = 7;  // kol-vo podmnogestv
static int n = 9;  // kol-vo elementov polnogo mnogestva
 
void main()
{ int i;
  U = 0; // Togda polnoe mnojestvo delaetsya tak:
  for(i=0; i<n;i++ )   U |= (1L<<i);
//  printf ("U = %lx\n", U); // DEB
  Pokr(0, 0L, 0L);
}
/*****************/
// Y - pokrito  P - who ispol'zovan J - s kakovo nachinat'
Pokr(int J, long Y, long P)
{ long Q, Z; int i, j; double s;
 
   for(i=J; i<N; i++) {
     if (((Y^A[i]) & (Y^U))==0) continue; // A[i] nichego ne dobavit
     Z = (Y|A[i]);
     Q = (P|(1L<<i));
     if (Z==U) {
        // printf("Z=%lx i=%d\n", Z, i); // DEB
        s = 0;
        for (j=0; j<N; j++) { // Pechat' naydennogo pokrytiya i ego ceny
          if ( (Q & (1L<<j))!=0 ) {
            printf("%c ", 'A'+j);
            s += a[j];
          }
        }
        printf("s=%f\n", s);
        continue;
     }
     Pokr(i+1, Z, Q); // Recursia!
   }
}
/*****************/