C++没学好,导致这学期的算法课程完全不行,求一个大佬指导一下
用动态规划实现完全背包问题
输入:物品个数、背包限重、物品重量和价值
输出:解向量
参考教材:算法分析与设计(第2版)屈婉玲等编著
#include<iostream>
#include <iomanip>
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全部需要动态内存分配
}
Knapsack::~Knapsack()
{
// 释放a,F,S,x的内存空间
}
void Knapsack::DP()
{
// 该函数就是计算Fk(y)和ik( y )
// 教材上没有算法,请根据课件讲的例子,搞清楚计算过程,自己填写代码
}
void Knapsack::Tracksolution()
{
// 可以参考教材65页算法3.3
}
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 n,b;
cout<<"input number of articles, n=";
cin>>n;
cout<<"input backpack limited capacity, b=";
cin>>b;
Knapsack mike(n,b);
mike.input();
mike.DP();
mike.Tracksolution();
mike.output();
return 0;
}