#include<iostream>
#include <iomanip>
#include <float.h>
#include <math.h>
using namespace std;
struct articles // 定义物品结点
{ int w; //重量
int v; //价值
};
class Knapsack //定义背包类
{
public:
Knapsack(int num,int wb); // 构造函数，num为物品数量，wb背包限制容量
~Knapsack(); // 析构函数
void DP(); // 动态规划算法实现（生成优化函数和标记函数）
void Tracksolution(); // 解的跟踪
void input(); // 输入数据
void output(); // 输出数据
private:
int n; // 物品个数
int b; // 背包限重
articles * a; // 物品数组
int ** F; // 优化函数F
int ** S; // 标记函数S，就是教材的ik( y )（64页）
int * x; // 解向量,存放结果
};
Knapsack::Knapsack(int num,int wb) //构造函数
{
// 对私有数据成员进行初始化，注意a,F,S,x全部需要动态内存分配
n=num;
b=wb;
articles *a=new articles[n+1];
cout<<"input weight：";
for(int i=1;i<=n;i++)
cin>>a[i].w;
cout<<"input value：";
for(int i=1;i<=n;i++)
cin>>a[i].v;
int **F=new int*[n+1];
for(int i=0;i<=n;i++){
F[i]=new int[b+1];
}
int **S=new int*[n+1];
for(int i=0;i<=n;i++){
S[i]=new int[b+1];
}
int *x=new int[n+1];
}
Knapsack::~Knapsack()
{
// 释放a,F,S,x的内存空间
delete []a;
delete []F;
delete []S;
delete []x;
}
void Knapsack::DP()
{
for(int i=0;i<=b;i++)
F[0][i]=0;
for(int i=0;i<=n;i++)
F[i][0]=0;
for(int i=0;i<=b;i++)
S[0][i]=0;
for(int i=0;i<=n;i++)
S[i][0]=0;
for(int i=0;i<=b;i++)
F[1][i]=floor(i/a[1].w*a[1].v);
for(int i=0;i<=n;i++)
for(int j=0;j<=b;j++){
if(j<0);
F[i][j]=-DBL_MAX;
}
for(int i=0;i<=n;i++)
for(int j=0;j<=b;j++){
if(F[i-1][j]<=F[i][j-a[i].w]+a[i].v){
F[i][j]=F[i][j-a[i].w]+a[i].v;
S[i][j]=i;
}
else{
F[i][j]=F[i-1][j];
S[i][j]=S[i-1][j];
}
}
// 该函数就是计算Fk(y)和ik( y )
// 教材上没有算法，请根据课件讲的例子，搞清楚计算过程，自己填写代码
}
void Knapsack::Tracksolution()
{
int y,j;
// 可以参考教材65页算法3.3
for(int j=1;j<=n;j++)
x[j]=0;
y=b;
j=n;
while(S[j][y]!=0){
j=S[j][y];
x[j]=1;
y=y-a[j].w;
while(S[j][y]==j){
y=y-a[j].w;
x[j]++;
}
}
}
/*void Knapsack::input()
{
cout<<"input weight：";
for(int i=1;i<=n;i++)
cin>>a[i].w;
cout<<"input value：";
for(int i=1;i<=n;i++)
cin>>a[i].v;
}*/
void Knapsack::output()
{
for(int i=0;i<=n;i++) //输出二维数组F，可省略
{ for(int j=0;j<=b;j++)
cout<<setw(4)<<F[i][j];
cout<<endl;
}
cout<<endl;
for(int i=0;i<=n;i++) //输出二维数组S，可省略
{ for(int j=0;j<=b;j++)
cout<<S[i][j]<<" ";
cout<<endl;
}
cout<<endl;
cout<<"x=<"; //输出解向量
for(int i=1;i<=n;i++)
cout<<x[i]<<", ";
cout<<x[n]<<">"<<endl;
}
int main()
{ int num,wb;
cout<<"input number of articles, n=";
cin>>num;
cout<<"input backpack limited capacity, b=";
cin>>wb;
Knapsack mike(num,wb);
// mike.input();
mike.DP();
mike.Tracksolution();
mike.output();
return 0;
}
