背包问题 急 在线等

Question

有不同价值，不同重量的物品N件，从这些中随便选出一部分物品的方案，使的总重量不超过指定的重量，但是价值最大，写一个程序

Answer 1

#include<iostream>
#include<fstream>
#include<memory>
using namespace std;
int min(int,int);
int max(int,int);
void init();
void knap();
void cal_res();
void traceback();
void show_res();
int *w,*v,*x,**m,c,n,total;
/*****************************************************/
void main()
{
init();
knap();
traceback();
cal_res();
show_res();
}
/*******************************************/
void init()
{
 fstream in("in.txt");
in>>n;
in>>c;
    w=new int[n+1]; memset(w,0,(n+1)*sizeof(int));
v=new int[n+1]; memset(v,0,(n+1)*sizeof(int));
    x=new int[n+1]; memset(x,0,(n+1)*sizeof(int));
int count(1);
while(count<=n)
{
  in>>w[count++];
}
    count=1;
while(count<=n)
{
 in>>v[count++];
}
in.close();
    m=new int*[n+1];
    for(int i=0;i<=n;i++)
{
m[i]=new int[c+1];
        memset(m[i],0,(c+1)*sizeof(int));
}
}
/*****************************************************/
int min(int x1,int x2)
{
return x1>x2 ? x2:x1;
}
int max(int x1,int x2)
{
    return x1>x2 ? x1:x2; 
}
/********************************************************/
void knap()
{
     int nn=n;
     int jmax=min(w[nn]-1,c);
     for(int j=w[nn];j<=c;j++)
     m[nn][j]=v[nn]; 
 for(int i=nn-1;i>1;i--)
 {
    jmax=min(w[i]-1,c);
    for(int j=0;j<=jmax;j++)
        m[i][j]=m[i+1][j];
    for(j=w[i];j<=c;j++)
m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
 }
         m[1][c]=m[2][c];
        if(c>w[1])
         m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
}
/****************************************************/
void traceback()
{
  int nn=n;
  for(int i=1;i<nn;i++)
  if(m[i][c]!=m[i+1][c])
  { 
  x[i]=1;
  c-=w[i];
  }
  x[nn]=(m[nn][c]>0)?1:0;
}
/*******************************************************/
void cal_res()
{
  total=0;
  for(int i=1;i<=n;i++)
   total+=x[i]*v[i];}
/*****************************************************/
void show_res()
{
   cout<<"结果已送至'out.txt'文件"<<endl;

ofstream out("out.txt");
    out<<"最优解为：\t";
for(int i=1;i<=n;i++)
  out<<x[i]<<"  ";
out<<endl;
out<<"总效益为\t"<<total<<endl;
}

Answer 2

注意v为效益矩阵,w为重量矩阵，|x为解