您现在的位置是:首页 > 正文

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

2024-04-01 03:25:51阅读 2

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

 

网站文章

  • 关于清空浏览器中cookie中所有数据的内容信息

    关于清空浏览器中cookie中所有数据的内容信息

    清空浏览器中cookie中所有的数据信息内容,看到有很多是重写cookie中的信息,感觉不是多么合适,不适合自己使用方式,全部清空缓存信息需要删除里面的所有信息。在方法中直接添加该段代码就能清空cookie中所有的数据信息。

    2024-04-01 03:25:43
  • Es性能优化

    Es性能优化

    1. Es中10亿级别的数据量,如何提高查询效率(1) 性能优化关键:file system cachea. 不要期待随手挑一个参数,就可以万能的应对所有性能慢的场景b. es依赖于底层的file system cache,如果给file system cache更多的内存,尽量让内存容纳所有的idx segment file索引数据文件,则搜索时均走内存,性能很高。如果内存...

    2024-04-01 03:25:03
  • 【前端】IIS部署前端

    【前端】IIS部署前端

    3.双击“Application Request Routing”,在右侧操作中点击“Proxy”中的“Server Proxy Settings...”,然后将“Enable proxy”打上勾即可...

    2024-04-01 03:24:55
  • Nacos系列-Nacos配置中心

    Nacos系列-Nacos配置中心

    接下来本系列博客将会整理Nacos的相关知识,主要将会涉及到 服务注册与发现、配置管理、分布式系统个、高可用和容错性、配置文件格式和解析几个方面。今天就先从配置管理讲起,看看如何使用nacos的配置管理,它能够给我们带来什么~Nacos(全名为阿里巴巴中间件 NACOS,前身为阿里巴巴注册中心和配置中心)是一款用于实现微服务架构中配置管理和服务发现的开源产品。

    2024-04-01 03:24:46
  • 有关import sun.audio.AudioPlayer(或者其它文件)的问题

      今天白天在工作中使用Eclipse编译代码的时候,在播放声音的代码中报了这么一个错误   import sun.audio.AudioPlayer;   import sun.audio.AudioStream;   上面这两句都报“Access restriction: The type AudioPlayer is not accessible due to restrictio...

    2024-04-01 03:24:05
  • 将前端代码布置到服务器端后找不到静态资源

    将前端代码布置到服务器端后找不到静态资源

    将前端页面代码布置到服务器SpringMVC后,经常出现静态资源找不到的问题。 首先,应该设置springMVC,使其不要拦截静态资源。在springMVC的配置文件中添加如下代码:

    2024-04-01 03:23:59
  • 脚本forfiles(文件的查找和删除)

    脚本forfiles(文件的查找和删除)

    显示当前目录下的内容 不在要查找的目录上 -p:指定的路径 forfiles /p F:\data /m 查找的文件名掩码 forfiles /p F:\data -m *.pdf 查找不同类型的文件...

    2024-04-01 03:23:52
  • 动态播放幻灯片 计算机教案,小学信息技术《动态播放幻灯片-设置幻灯片文字的动画效果》教案...

    动态播放幻灯片 计算机教案,小学信息技术《动态播放幻灯片-设置幻灯片文字的动画效果》教案...

    一、教学目标1.能独立设置幻灯片文字的动画效果,合理选择动画效果。2.通过小组合作设置有个性的动画效果,锻炼学生的合作探究能力以及创新精神。3.通过本节课的学习,体会成功的喜悦,增强自信心,激发学生对...

    2024-04-01 03:23:10
  • storj简介

    storj简介

    概述Storj,这是来自美国StorjLabs公司旗下的项目,是在2014年首次被提出的,总共做了两次募资,第一次众筹了约50万美元,在上线测试版之后也就是2017年又进行了一次1CO,这次共筹得了约...

    2024-04-01 03:23:02
  • No value specified 报错

    今天遇到了 No value specified 这个问题:在控制台报了这样的错误:org.apache.commons.beanutils.ConversionException: No value specified at org.apache.commons.beanutils.converters.BigDecimalConverter.convert(BigDecimalC

    2024-04-01 03:22:56