我想用动态规划解决背包问题！物品应该在背包里还是不在背包里，我不想把同一件物品放在背包里超过一次！
我已经看过这段代码了，但是使用这段代码，您可以多次添加同一个对象，而不是一次

#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;
}

你们能帮我一下吗？：）