{"id":288,"date":"2006-03-25T10:54:00","date_gmt":"2006-03-25T10:54:00","guid":{"rendered":"http:\/\/fanhaijun.com\/?p=288"},"modified":"2006-03-25T10:54:00","modified_gmt":"2006-03-25T10:54:00","slug":"%e8%83%8c%e5%8c%85%e7%ae%97%e6%b3%95","status":"publish","type":"post","link":"https:\/\/fanhaijun.com\/?p=288","title":{"rendered":"\u80cc\u5305\u7b97\u6cd5"},"content":{"rendered":"

#include <iostream.h>
#include<iomanip.h>
#include<string.h>
int min(int w,int c)
{int temp;
 if (w<c) temp=w;
 else
 temp=c;
 return temp;
}
int max(int w,int c)
{
 int temp;
 if (w>c) temp=w;
 else
 temp=c;
 return temp;
}
void knapsack(int v[],int w[],int c,int n,int**m)      \/\/\u6c42\u6700\u4f18\u503c
{
  int jmax=min(w[n]-1,c);
  for(int j=0;j<=jmax;j++)
    m[n][j]=0;
  for(int jj=w[n];jj<=c;jj++)
    m[n][jj]=v[n];
  for(int i=n-1;i>1;i–){                           \/\/\u9012\u5f52\u90e8\u5206
    jmax=min(w[i]-1,c);
    for(int j=0;j<=jmax;j++)
      m[i][j]=m[i+1][j];
    for(int jj=w[i];jj<=c;jj++)
      m[i][jj]=max(m[i+1][jj],m[i+1][jj-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]);
 cout<<"\u6700\u4f18\u503c\uff1a"<<m[1][c]<<endl;
 for(int l=2;l<=n;l++)
  for(int j=0;j<=c;j++)
  {
   cout<<m[l][j]<<setw(c-1);
 }    
  cout<<endl;
  cout<<"*******************************************"<<endl;
}<\/p>\n

int traceback(int **m,int w[],int c,int n,int x[])      \/\/\u56de\u4ee3\uff0c\u6c42\u6700\u4f18\u89e3
{
 cout<<"\u5f97\u5230\u7684\u4e00\u7ec4\u6700\u4f18\u89e3\u5982\u4e0b:"<<endl;
  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];}
  x[n]=(m[n][c])?1:0;
  for(int y=1;y<=n;y++)
  {
   cout<<setw(5)<<x[y];
  }
  return x[n];
  
}
void main()
{
 int n,c;
 int **m;
 cout<<"&&&&&&&&&&&&&&&&&&&&&\u6b22\u8fce\u4f7f\u75280-1\u80cc\u5305\u95ee\u9898\u7a0b\u5e8f&&&&&&&&&&&&&&&&&&&"<<endl;
 cout<<"\u8bf7\u8f93\u5165\u7269\u54c1\u4e2a\u6570\u548c\u91cd\u91cf\u4e0a\u9650:";
 cin>>n>>c;
   int *v=new int[n+1];
 cout<<"Pls input the property (v[i]):"<<endl;
 for(int i=1;i<=n;i++)
  cin>>v[i];
 int *w=new int[n+1];
 cout<<"Pls input the weight (w[i]):"<<endl;
 for(int j=1;j<=n;j++)
  cin>>w[j];
 int *x=new int[n+1];
 m=new int*[n+1];  \/\/\u52a8\u6001\u7684\u5206\u914d\u4e8c\u7ef4\u6570\u7ec4
 for(int p=0;p<n+1;p++)
 {
  m[p]=new int[c+1];
} 
 
 knapsack(v,w,c,n,m);
 traceback(m,w,c,n,x);<\/p>\n

}<\/p>\n","protected":false},"excerpt":{"rendered":"

#include <iostream.h&g…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_lmt_disableupdate":"","_lmt_disable":"","footnotes":""},"categories":[101],"tags":[],"class_list":["post-288","post","type-post","status-publish","format-standard","hentry","category-college-life"],"_links":{"self":[{"href":"https:\/\/fanhaijun.com\/index.php?rest_route=\/wp\/v2\/posts\/288","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fanhaijun.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fanhaijun.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fanhaijun.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/fanhaijun.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=288"}],"version-history":[{"count":0,"href":"https:\/\/fanhaijun.com\/index.php?rest_route=\/wp\/v2\/posts\/288\/revisions"}],"wp:attachment":[{"href":"https:\/\/fanhaijun.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=288"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fanhaijun.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=288"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fanhaijun.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=288"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}