编辑代码

#include "stdafx.h";
#include <iostream>;
using namespace std;

#define c   10
#define n    5

void Knapsack(int *w, int *v, int n, int c, int (*m)[C+1])
{
     int lowc=w[n]-1>c?c :w[n]-1; 
     for (int j = 0; j <= lowc; j++) 
    m[n][j] = 0; 
    for (int j = lowc+1; j <= c; j++) 
     m[n][j] =v[n];
     for (int i = n-1; i >1;i--)
    {
         lowc=w[i]-1>c?c:w[i]-1; 
         for(int j = 0; j <=lowc; j++) 
          m[i][j] = m[i+1][j]; 
         for(int j=lowc+1;j<c;j++)
         {
              int t1 =m[i+1][j]; 
              int t2=m[i+1][j-w[i]] +v[i]; 
                  m[i][i] =t1 >t2 ?t1 :t2; 
         }
    }
                  m[1][c] = m[2][c];
              if(c >= w[1] && m[2][c-w[1]] + v[1] >m[2][c])
                  m[1][c] = m[2][c-w[1]] +v[1];
}
          void Traceback(int (*m)[C+1],int *w, int *x,int n, int c)
{
          for (int i = 1; i < n; i++) 
  {
          if(m[i][c] == m[i+1][c]) 
               x[i] = 0;
        else
{
      x[i] = 1; 
      c -=w[i]; 
  } 
}
     w[n]<c?x[n] =1:x[n] =0;
}
int_tmain() {
  int x[N+1]; 
  int w[N+1] ={-1,2,2,6,5,4}; 
  int v[N+1] ={-1,6,3,5,4,6}; 
  int m[N+1][C+1]; 
  Knapsack(w,v,N,C,m); 
 cout<<m[1][c]<<endl; 
  Traceback(m, w, x,N, C);
  for(int i=1;i<=N；i++)
  {
      cout<<x[i]<<" ";
  }
  cout<<endl;
  system("pause");
  return o;
}