Блог

Я хочу решить проблему рюкзака с помощью динамического программирования! Предмет должен быть в рюкзаке или нет, я не хочу класть один и тот же предмет в рюкзак более одного раза!

Я просмотрел этот код, но с помощью этого вы можете добавлять один и тот же объект более одного раза

 #include <stdio.h>

#define MAXWEIGHT 100

int n = 3; /* The number of objects */
int c[10] = {8, 6, 4}; /* c[i] is the *COST* of the ith object; i.e. what
                YOU PAY to take the object */
int v[10] = {16, 10, 7}; /* v[i] is the *VALUE* of the ith object; i.e.
                what YOU GET for taking the object */
int W = 10; /* The maximum weight you can take */ 

void fill_sack() {
    int a[MAXWEIGHT]; /* a[i] holds the maximum value that can be obtained
                using at most i weight */
    int last_added[MAXWEIGHT]; /* I use this to calculate which object were
                    added */
    int i, j;
    int aux;

    for (i = 0; i <= W;   i) {
        a[i] = 0;
        last_added[i] = -1;
    }

    a[0] = 0;
    for (i = 1; i <= W;   i)
        for (j = 0; j < n;   j)
            if ((c[j] <= i) amp;amp; (a[i] < a[i - c[j]]   v[j])) {
                a[i] = a[i - c[j]]   v[j];
                last_added[i] = j;
            }

    for (i = 0; i <= W;   i)
        if (last_added[i] != -1)
            printf("Weight %d; Benefit: %d; To reach this weight I added object %d (%d$ %dKg) to weight %d.n", 
                         i, a[i], last_added[i]   1, v[last_added[i]], 
                         c[last_added[i]], i - c[last_added[i]]);
        else
            printf("Weight %d; Benefit: 0; Can't reach this exact weight.n", i);

    printf("---n");

    aux = W;
    while ((aux > 0) amp;amp; (last_added[aux] != -1)) {
        printf("Added object %d (%d$ %dKg). Space left: %dn", 
               last_added[aux]   1, v[last_added[aux]], 
               c[last_added[aux]], aux - c[last_added[aux]]);
        aux -= c[last_added[aux]];
    }

    printf("Total value added: %d$n", a[W]);
}

int main(int argc, char *argv[]) {
    fill_sack();

    return 0;
}
  

и затем я попытался создать массив, чтобы увидеть, находится ли объект в рюкзаке или нет, но тогда эта программа не работала должным образом!

 #define MAXWEIGHT 101
#define MAX_ITEMS 100000

int items = 2;
int c[10] = {1, 2};
int v[10] = {1000, 2001};
int W = 100;
int taken[MAX_ITEMS];

void takenOrNot(){
  int i;

  for(i = 0; i < items; i  ){
    taken[i] = 0;
  }
}
void fill_sack() {
  int a[MAXWEIGHT];
  int last_added[MAXWEIGHT];
  int i, j;
  int aux;

  for (i = 0; i <= W;   i) {
    a[i] = 0;
    last_added[i] = -1;
  }

  a[0] = 0;
  for (i = 1; i <= W;   i)
    for (j = 0; j < items;   j)
        if ((c[j] <= i) amp;amp; (a[i] < a[i - c[j]]   v[j]) amp;amp; taken[j] == 0) {
            a[i] = a[i - c[j]]   v[j];
            last_added[i] = j;
            taken[j] = 1;
        }

  for (i = 0; i <= W;   i)
    if (last_added[i] != -1)
      printf("Weight %d; Benefit: %d; To reach this weight I added object %d (%d$ %dKg) to weight %d.n", 
           i, a[i], last_added[i]   1, v[last_added[i]], 
           c[last_added[i]], i - c[last_added[i]]);
    else
      printf("Weight %d; Benefit: 0; Can't reach this exact weight.n", i);

  printf("---n");

  aux = W;
  while ((aux > 0) amp;amp; (last_added[aux] != -1)) {
    printf("Added object %d (%d$ %dKg). Space left: %dn", 
        last_added[aux]   1, v[last_added[aux]], 
        c[last_added[aux]], aux - c[last_added[aux]]);
    aux -= c[last_added[aux]];
  }

  printf("Total value added: %d$n", a[W]);
}

int main(int argc, char *argv[]) {

  takenOrNot();
  fill_sack();

  return 0;
}
  

Ребята, не могли бы вы мне помочь, пожалуйста? 🙂

Это могло бы помочь …!

 public class Knapsack
{
    int knapsackSize;
    int[] _weights;
    int[] _values;
    int[,] results;


    public Knapsack(int[] weights, int[] values, int size)
    {
        _weights = weights;
        _values = values;
        knapsackSize = size;
    }

    public int CreateSolution()
    {
        results = new int[_weights.Length   1, knapsackSize   1];

        for (int i = 0; i < _weights.Length; i  )   // item 1 to n
        {
            for (int j = 1; j <= knapsackSize; j  ) //weight 1 to m
            {
                if (_weights[i] > j)
                {
                    //if item weight is grater than knapsack capacity
                    results[i   1, j] = results[i, j];
                }

                else
                {
                    if (results[i, j] > (_values[i]   results[i, j - _weights[i]]))
                    {
                        //if previously calculated value only is grater
                        results[i   1, j] = results[i, j];
                    }
                    else
                    {
                        //if including current item gives more value
                        results[i   1, j] = _values[i]   results[i, j - _weights[i]];
                    }
                }
            }
        }
        return results[_weights.Length, knapsackSize]; // index (n, m) will be max value
    }

    static void Main(string[] args)
    {
        Knapsack demo = new Knapsack(new int[] { 23, 26, 20, 18, 32, 27, 29, 26, 30, 27 }, new int[] { 505, 352, 458, 220, 354, 414, 498, 545, 473, 543 }, 67);
        Console.WriteLine("Solution is: "   demo.CreateSolution());
        Console.ReadLine();
    }
}