knapsack.cc

#include<knapsack.h>

double
KNAPSACK (array < int >&W, int w, array < double >&C, set < int >&S)
{
  /*{\Mfunc Solves the knapsack problem. {\bf describe}} */
  array2 < double >G (-1, W.high (), 0, w);

  for (int i = 0; i <= w; i++)
    G (-1, i) = -1;
  G (-1, 0) = 0;

  for (int i = 0; i <= W.high (); i++)
    {
      for (int j = 0; j <= w; j++)
        if (j < W[i])
          G (i, j) = G (i - 1, j);
        else
          G (i, j) = leda_max (G (i - 1, j), G (i - 1, j - W[i]) + C[i]);
    }

  int j = 0;
  for (int i = 0; i <= w; i++)
    if (G (W.high (), i) > G (W.high (), j))
      j = i;

  int i = j;
  for (int k = W.high (); k >= 0; k--)
    {
      if (G (k - 1, i) != G (k, i))
        {
          i -= W[k];
          S.insert (k);
        }
    }

  return G (W.high (), j);
}



double
KNAPSACK (map < int, int >&W, map < int, double >&C, int w, set < int >&S)
{                               //, set< map<int,int> >& GP) {
  /*{\Mfunc Solves the knapsack problem, where $C$ maps the items to their costs,
     $W$ maps the items to their wheight, and $w$ is the wheigt limit.
     The solution is stored in $S$. } */
  map < int, list < KE > >G;
  int i, last = -1;
  list_item l1, l2;
  S.clear ();

  forall_defined (i, W)
  {
    if (last == -1)
      {
        G[i].append (KE (W[i], C[i], nil, 0));
        G[i].append (KE (0, 0, nil, 0));
      }
    else
      {
        l2 = G[last].first_item ();
        forall_items (l1, G[last])
        {
          while ((l2 != nil)
                 && (G[last][l2].first () < G[last][l1].first () + W[i]))
            {
              G[i].append (KE (G[last][l2].first (),
                               G[last][l2].second (), l2, last));
              l2 = G[last].next_item (l2);
            }
          if ((l2 != nil)
              && (G[last][l2].first () == G[last][l1].first () + W[i]))
            {
              if (G[last][l2].second () > G[last][l1].second () + C[i])
                G[i].append (KE (G[last][l2].first (),
                                 G[last][l2].second (), l2, last));
              else
                G[i].append (KE (G[last][l1].first () + W[i],
                                 G[last][l1].second () + C[i], l1, last));
            }
          else
            {
              if (G[last][l1].first () + W[i] <= w)
                G[i].append (KE (G[last][l1].first () + W[i],
                                 G[last][l1].second () + C[i], l1, last));
            }
        }
      }
    last = i;
  }
  l2 = G[last].first_item ();
  forall_items (l1,
                G[last]) if (G[last][l1].second () >
                             G[last][l2].second ())l2 = l1;

  i = last;
  l1 = l2;
  int j;

  int w1 = G[last][l2].first ();

  while (G[i][l1].third () != nil)
    {
      j = G[i][l1].fourth ();
      l1 = G[i][l1].third ();
      if (G[j][l1].first () != w1)
        {
          S.insert (i);
        }
      i = j;
      w1 = G[i][l1].first ();
    };
  if (G[i][l1].first () != nil)
    {
      S.insert (i);
    }

  j = 0;
  forall_defined (i, W) j++;
  array < int >W2 (j);
  array < double >C2 (j);
  j = 0;
  forall_defined (i, W)
  {
    W2[j] = W[i];
    C2[j] = C[i];
    j++;
  }
  set < int >S2;
  if (KNAPSACK (W2, w, C2, S2) != G[last][l2].second ())
    cout << "knapsack error\n";

  return G[last][l2].second ();
};


double
KNAPSACK (map < int, int >&W, map < int, double >&C, int w,
          map < int, int >&S, map < int, int >&LB, map < int, int >&UB)
{
  /*{\Mfunc Solves the knapsack problem, where $C$ maps the items to their costs,
     $W$ maps the items to their wheight, $w$ is the wheigt limit, and $LB$ and 
     $UB$ are lower and upper bounds on the number of times a item can be used. 
     The solution is stored in $S$. } */
  S.clear ();

  int w1 = w;

  int i, j, k, l = 0;

  forall_defined (i, W)
  {
    j = UB[i] - LB[i];
    k = 1;
    while (2 * k - 1 < j)
      {
        l++;
        k = k * 2;
      };
    l++;
  }

  array < int >W1 (l + 1);
  array < double >C1 (l + 1);
  array < int >ON (l + 1);
  array < int >Nk (l + 1);

  l = 0;
  forall_defined (i, W)
  {
    j = UB[i] - LB[i];
    w1 -= LB[i] * W[i];
    k = 1;
    while (2 * k - 1 < j)
      {
        W1[l] = W[i] * k;
        C1[l] = C[i] * k;
        ON[l] = i;
        Nk[l] = k;
        l++;
        k = k * 2;
      };
    W1[l] = W[i] * (j - k + 1);
    C1[l] = C[i] * (j - k + 1);
    ON[l] = i;
    Nk[l] = j - k + 1;
    l++;
  }

  if (w1 < 0)
    {
      cout << w1 << " w1\n";
      return -10000;
    }

  set < int >S1;
  double d = KNAPSACK (W1, w1, C1, S1);

  forall (i, S1)
  {
    S[ON[i]] += Nk[i];
  }

  forall_defined (i, W)
  {
    S[i] += LB[i];
    d += LB[i] * C[i];
  }

  return d;
}

---