#include <iostream>
#include <string>
using namespace std;
const int N=4;
const int B=10;
void Knapsack(int v[N],int w[N],int F[][B+1],int tagi[][B+1]){
for(int k=0;k<=N;k++){
F[k][0]=0;
tagi[k][0]=0;
}
for(int y=0;y<=B;y++){
F[0][y]=0;
F[1][y]=(int)(y/w[0])*v[0];//只能装第一件物品时
tagi[0][y]=0;
}
for(int k=1;k<=N;k++){
for(int y=1;y<=B;y++){
if(y-w[k-1]<0){
F[k][y]=F[k-1][y];
tagi[k][y]=tagi[k-1][y];
}
else{
//允许装入k件物品，价值的两种情况：
//不装第k件物品或至少装1件第k件物品
F[k][y]=F[k-1][y]>F[k][y-w[k-1]]+v[k-1] ? F[k-1][y]:(F[k][y-w[k-1]]+v[k-1]);
tagi[k][y]=F[k-1][y]>F[k][y-w[k-1]]+v[k-1]?tagi[k-1][y]:k;
}
}
}
}
void TrackSolution(int v[N],int w[N],int tagi[][B+1]){
//x[i-1]标记第i件物品的件数
int x[N];
for(int i=0;i<N;i++)
x[i]=0;
int y=B,j=tagi[N][B];
while (tagi[j][y]!=0){
j=tagi[j][y];
//标记函数最下角ik(y)标记的物品取一件
x[j-1]=1;
y=y-w[j-1];
while (tagi[j][y]==j){
y=y-w[j];
x[j-1]=x[j-1]+1;
}
}
for(int i=0;i<N;i++)
cout<<" "<<x[i];
cout<<endl;
}
//打印优化函数和标记函数
void PrintFandTagi(int F[][B+1],int tagi[][B+1]){
cout<<"优化函数Fk(y)：\nK\\Y";
for(int i=1;i<=B;i++)
cout<<"\t"<<i;
cout<<endl;
for(int i=1;i<=N;i++){
cout<<i;
for(int j=1;j<=B;j++){
cout<<"\t"<<F[i][j];
}
cout<<endl;
}
cout<<"\n标记函数ik(y)：\nk\\y";
for(int i=1;i<=B;i++)
cout<<"\t"<<i;
cout<<endl;
for(int i=1;i<=N;i++){
cout<<i;
for(int j=1;j<=B;j++){
cout<<"\t"<<tagi[i][j];
}
cout<<endl;
}
}
int main(){
int v[N]={1,3,5,9};
int w[N]={2,3,4,7};
int F[N+1][B+1];
int tagi[N+1][B+1];
Knapsack(v,w,F,tagi);
cout<<" 最终装入每件物品的数量分别为：";
TrackSolution(v,w,tagi);
PrintFandTagi(F,tagi);
cout<<endl;
return 0;
}
main_knapsack.zip （1个子文件） 
main_knapsack.cpp 2KB
xiaowei_cqu
- 粉丝: 1w+
- 资源: 35
- 1
- 2
前往页