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; }