C/C++教程

动态规划实现完全背包问题C++【求助】

本文主要是介绍动态规划实现完全背包问题C++【求助】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

 

这篇关于动态规划实现完全背包问题C++【求助】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!