背包问题1/0动态

Question

我想用动态编程解决背包问题！该物品是否应该放在背包里，我不想一次将同一物品放在背包里！

我看过这段代码，但是有了这个代码，您可以一次添加更多的对象

#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) && (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) && (last_added[aux] != -1)) {
        printf("Added object %d (%d$ %dKg). Space left: %d\n", 
               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) && (a[i] < a[i - c[j]] + v[j]) && 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) && (last_added[aux] != -1)) {
    printf("Added object %d (%d$ %dKg). Space left: %d\n", 
        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;
}

你们能帮我吗？ :)

Answer 1

只需抬起头：

以下代码可通过this SO链接作为问题来使用。algorithms.h头文件位于my Github repo

#include "algorithms.h"

struct Item {
    int index = 1;
    int profit = 1;
    int weight = 1;
    Item() = delete;
    explicit Item(int i, int _profit, int w) {
        index = i;
        profit = _profit;
        weight = w;
    }
    bool operator<(const Item& item) {
        return this->profit < item.profit;
    }
    bool operator<=(const Item& item) {
        return this->profit <= item.profit;
    }
    bool operator>(const Item& item) {
        return this->profit > item.profit;
    }
    bool operator>=(const Item& item) {
        return this->profit >= item.profit;
    }
    friend std::ostream& operator<<(std::ostream& out, const Item item) {
        out << item.index;
        return out;
    }
};

long weight(const std::vector<Item>& item_list, const std::vector<int>& item_switch) {
    long sum = 0;
    for (int i = 0; i < item_switch.size(); i++) {
        sum += item_switch[i] * item_list[i].weight;
    }
    return sum;
}

long profit(const std::vector<Item>& item_list, const std::vector<int>& item_switch) {
    long sum = 0;
    for (int i = 0; i < item_switch.size(); i++) {
        sum += item_switch[i] * item_list[i].profit;
    }
    return sum;
}

void increment(std::vector<int>& vec) {
    auto it_bit = vec.end();
    it_bit--;
    while (*it_bit == 1) {
        *it_bit = 0;
        if (it_bit == vec.begin()) {
            return;
        }
        it_bit--;
    }
    *it_bit = 1;
}

int main() {
    long M = 25;
    Item i1(1, 10, 9);
    Item i2(2, 12, 8);
    Item i3(3, 14, 12);
    Item i4(4, 16, 14);
    std::vector<Item> items = { i1,i2,i3,i4 };
    std::vector<int> enable(4,0);
    std::vector<std::vector<int>> possible;
    for (int i = 1; i <= 16; i++) {
        if (weight(items, enable) <= M) {
            possible.push_back(enable);
        }
        increment(enable);
    }
    long pr = 0;
    for (int i = 0; i < possible.size(); i++) {
        long temp = profit(items, possible[i]);
        if (temp > pr) {
            pr = temp;
        }
    }
    std::cout << pr;
    return 0;
}