编译语言的回溯
⑴ re从零开始的反编译教程
写在开头，引用很喜欢的一句话： 要么学！要么不学！学和不学之间没有中间值 不学就放弃,学就要去认真的学！ --致选择
为了回溯编译过程（或对程序进行逆向工程），我们使用各种工具来撤销汇编和编译过程，这些工具就叫反汇编器和反编译器。反汇编器撤销汇编过程，因此我们可以得到汇编语言形式的输出结果。反编译器则以汇编语言甚至是机器语言为输入，其输出结果为高级语言。
数组的表示方式是：在基本类型前加上前中括号“[”，例如int数组和float数组分别表示为：[I、[F；对象的表示则以L作为开头，格式是 LpackageName/objectName;
（注意必须有个分号跟在最后），例如String对象在smali中为： Ljava/lang/String; ，其中 java/lang 对应 java.lang 包，String就是定义在该包中的一个对象。或许有人问，既然类是用 LpackageName/objectName; 来表示，那类里面的内部类又如何在smali中引用呢？
答案是：在 LpackageName/objectName/subObjectName 的 subObjectName 前加 $ 符号。
方法的定义一般为： Func-Name (Para-Type1Para-Type2Para-Type3...)Return-Type
注意参数与参数之间没有任何分隔符，同样举几个例子就容易明白
无序列表的使用，在符号"-"后加空格使用。如下：
https://www.jianshu.com/p/1c54c1ccf5cc
https://www.cnblogs.com/onelikeone/p/7594177.html
解决：点击进去jd-gui，删除试一试。再不行换最新版本
解析结束后进行编译报错
解决方法： https://blog.csdn.net/fuchaosz/article/details/104800802
Failed parse ring installPackageLI: Targeting R+ (version 30 and above) requires the resources.arsc of installed APKs to be stored uncompress
解决方法：
降低gradle里版本，若出现
signatures do not match the previously installed version; ，
使用adb install命令在手机上安装app时，遇到这个报错。原因是新装的app和手机上现有的旧版app冲突了。
解决方法：删除手机上原来的app，再重新安装即可。
可是转念一想如果反编译的apk都是Version 30 R+以上，难道我解压后挨个改一遍gradle？太彻淡了，一定有解决方法，所以有了下面探究出现这个问题的解决方法：既然报错是资源文件高版本不支持，而且没有4位对齐，那么不编译资源文件就好了
APK签名工具之jarsigner和apksigner：
https://blog.csdn.net/xzytl60937234/article/details/89088215?utm_medium=distribute.pc_relevant.none-task-blog-js_landingword-1&spm=1001.2101.3001.4242
利用apktool反编译apk，并且重新签名打包：
https://blog.csdn.net/qq_21007661/article/details/109851522?utm_medium=distribute.pc_relevant.none-task-blog-js_title-4&spm=1001.2101.3001.4242
验证apktool能否使用
apktool -r d apk名字.apk，不反编译资源文件，为什么这么做，先挖个坑
错误提示没有4位对齐和不支持30版本以上的资源文件。所有尝试不编译资源文件
解决4位对齐的方法：
查看当前目录，生成了新文件：abc.keystor
使用JarSigner对apk进行签名，命令如下
jarsigner -verbose -keystore abc.keystore -signedjar testx.apk src.apk abc.keystore
直接反编译的apk产生上述错误
但是只编译资源文件的apk安装时
发现没有使用V2进行签名，这时候进行V2签名， (apksigner,默认同时使用V1和V2签名 ）
所以先对只编译资源文件的apk进行V2尝试看能否成功
重复1（进行apktool -r d apk名字.apk）-->2 -->3 -->4( 不使用jarsigner而使用apksigner )
将生成的abc.keystore和打包回的apk（ apktoolapp-debugdist 里的app-debug.apk）放入 C:Users aowei.lianAppDataLocalAndroidSdkuild-tools30.0.3 下，因为Android studio的SDK下有apksigner.bat.
对jarsigner只是apk进行了V1签名；在Android7.0引入了V2签名，因此，当进入sdk25.0.0及后续版本，会发现一个apksigner.bat执行脚本。
我们可以通过apksigner进行V2签名，当然，apksigner默认是同时支持V1与V2的，于是：
学习了公钥和密钥的使用和区别，使用私钥的加密算法称为对称加密算法，这种算法实现是接收方和发送方公用一道密钥，优点是效率高，缺点是安全性差，如果被第三人得知密钥则信息泄露，由此衍生了公钥加密算法，也就是非对称加密算法，这个算法是接收方给发送方公钥，发送方用公钥加密后发给接收方，接受方再用私钥解密。这样即使所有人知道公钥也不会造成信息泄露。缺点是效率非常低。
此外了解了RSA签名的大致过程，发送方拥有公钥和私钥，对信息进行摘要然后把摘要通过密钥进行签名，然后把签名和信息一起发出去，那么如何验证该信息就是发送方发出的呢，这时候就使用到了公钥验证，通过公钥对信息进行解签，然后使用一样的摘要算法得到摘要，如果得到的摘要和解签后的内容一致则说明是发送方发出。
总结就是公钥加密，私钥解密。公钥验证，私钥签名
RSA 密码体制是一种公钥密码体制，公钥公开，私钥保密，它的加密解密算法是公开的。由公钥加密的内容可以并且只能由私钥进行解密，而由私钥加密的内容可以并且只能由公钥进行解密。也就是说，RSA 的这一对公钥、私钥都可以用来加密和解密，并且一方加密的内容可以由并且只能由对方进行解密。
因为公钥是公开的，任何公钥持有者都可以将想要发送给私钥持有者的信息进行加密后发送，而这个信息只有私钥持有者才能解密。
它和加密有什么区别呢？因为公钥是公开的，所以任何持有公钥的人都能解密私钥加密过的密文，所以这个过程并不能保证消息的安全性，但是它却能保证消息来源的准确性和不可否认性，也就是说，如果使用公钥能正常解密某一个密文，那么就能证明这段密文一定是由私钥持有者发布的，而不是其他第三方发布的，并且私钥持有者不能否认他曾经发布过该消息。故此将该过程称为“签名”。
Android 签名机制 v1、v2、v3
进入JDK/bin, 输入命令
参数:
进入Android SDK/build-tools/SDK版本, 输入命令
参数:
例如:
最后安装加 -t ：
附上参考链接：
https://blog.csdn.net/A807296772/article/details/102298970
配置NDK的时候如果按钮是灰色的，手动配置
直接在javac后面指定编码是UTF-8就是了。
需要注意的是要加上* -classpath .其中classpath后面的一个黑点是不能省略的。
编译好后如何导入so库
成功运行后发现lib目录下已经apk编进去so了
https://www.52pojie.cn/thread-732298-1-1.html
本节所有到的工具和Demo
IDA
链接： https://pan..com/s/15uCX8o6tTSSelgG_RN7kBQ
Demo
链接： https://pan..com/s/1vKC1SevvHfeI7f0d2c6IqQ
找到so并打开它 因为我的机型是支持arm的所以我这里打开的是armeabi文件夹下的so 如果机型是x86模式的那么这里要打开x86模式下的libJniTest.so
编译过程：
按住键盘组合键 shift + f12 打开字符串窗口 这个窗口将会列举出so中所包含的所有字符串 因为上节课我们只编写了一个字符串 所以这里只有一个hello 52pojie! 如果打开的是x86的so这里还会有一些.so 但是字符串只有这一个
鼠标点在hello 52pojie!字符串上,打开 Hex mp窗口,修改hello 52pojie!对应内存地址的内容
关于字符对应的16进制可以在网络搜索ascii码表 找到字符所对应的16进制
因为我要把hello 52pojie！修改成hello world! 是不是只要找到每个字符所对应的hex修改就好了
这里我看到 hello 52pojie!对应的hex是:68 65 6C 6C 6F 20 35 32 70 6F 6A 69 65 21
我在ascii码表上找到world所对应的十六进制是:77 6F 72 6C 64
所以hello world! 对应的十六进制是:68 65 6C 6C 6F 20 77 6F 72 6C 64 21
注意编辑的时候光标暂停的位置只有先输入字母才能更改成功，修改好后 右键Apply changes应用
退出后保存
此时已经so修改完毕
大功告成，hello 52pojie! --> hello world!
⑵ 编译原理的发展历程
在20世纪40年代，由于冯·诺伊曼在存储-程序计算机方面的先锋作用，编写一串代码或程序已成必要，这样计算机就可以执行所需的计算。开始时，这些程序都是用机器语言 （machine language ）编写的。机器语言就是表示机器实际操作的数字代码，例如：
C7 06 0000 0002 表示在IBM PC 上使用的Intel 8x86处理器将数字2移至地址0 0 0 0 （16进制）的指令。
但编写这样的代码是十分费时和乏味的，这种代码形式很快就被汇编语言（assembly language ）代替了。在汇编语言中，都是以符号形式给出指令和存储地址的。例如，汇编语言指令 MOV X,2 就与前面的机器指令等价（假设符号存储地址X是0 0 0 0 ）。汇编程序（assembler ）将汇编语言的符号代码和存储地址翻译成与机器语言相对应的数字代码。
汇编语言大大提高了编程的速度和准确度，人们至今仍在使用着它，在编码需要极快的速度和极高的简洁程度时尤为如此。但是，汇编语言也有许多缺点：编写起来也不容易，阅读和理解很难；而且汇编语言的编写严格依赖于特定的机器，所以为一台计算机编写的代码在应用于另一台计算机时必须完全重写。
发展编程技术的下一个重要步骤就是以一个更类似于数学定义或自然语言的简洁形式来编写程序的操作，它应与任何机器都无关，而且也可由一个程序翻译为可执行的代码。例如，前面的汇编语言代码可以写成一个简洁的与机器无关的形式 x = 2。
在1954年至1957年期间，IBM的John Backus带领的一个研究小组对FORTRAN语言及其编译器的开发，使得上面的担忧不必要了。但是，由于当时处理中所涉及到的大多数程序设计语言的翻译并不为人所掌握，所以这个项目的成功也伴随着巨大的辛劳。几乎与此同时，人们也在开发着第一个编译器， Noam Chomsky开始了他的自然语言结构的研究。他的发现最终使得编译器结构异常简单，甚至还带有了一些自动化。Chomsky的研究导致了根据语言文法（grammar ，指定其结构的规则）的难易程度以及识别它们所需的算法来为语言分类。正如现在所称的-与乔姆斯基分类结构（Chomsky hierarchy ）一样-包括了文法的4个层次：0型、1型、2型和3型文法，且其中的每一个都是其前者的专门化。2型（或上下文无关文法（context-free grammar ））被证明是程序设计语言中最有用的，而且今天它已代表着程序设计语言结构的标准方式。
分析问题（ parsing problem ，用于限定上下文无关语言的识别的有效算法）的研究是在20世纪60年代和70年代，它相当完善地解决了这一问题， 现在它已是编译理论的一个标准部分。它们与乔姆斯基的3型文法相对应。对它们的研究与乔姆斯基的研究几乎同时开始，并且引出了表示程序设计语言的单词（或称为记号）的符号方式。
人们接着又深化了生成有效的目标代码的方法，这就是最初的编译器，它们被一直使用至今。人们通常将其误称为优化技术（optimization technique ），但因其从未真正地得到过被优化了的目标代码而仅仅改进了它的有效性，因此实际上应称作代码改进技术（code improvement technique ）。
这些程序最初被称为编译程序-编译器，但更确切地应称为分析程序生成器 （parser generator ），这是因为它们仅仅能够自动处理编译的一部分。这些程序中最着名的是 Yacc （yet another compiler- compiler），它是由Steve Johnson在1975年为Unix系统编写的。
类似地，有穷自动机的研究也发展了另一种称为扫描程序生成器 （scanner generator ）的工具，Lex （与Yacc同时，由Mike Lesk为Unix系统开发的）是这其中的佼佼者。在20世纪70年代后期和80年代早期，大量的项目都关注于编译器其他部分的生成自动化，这其中就包括代码生成。这些尝试并未取得多少成功，这大概是因为操作太复杂而人们又对其不甚了解。
编译器设计最近的发展包括：首先，编译器包括了更为复杂的算法的应用程序，它用于推断或简化程序中的信息；这又与更为复杂的程序设计语言（可允许此类分析）的发展结合在一起。其中典型的有用于函数语言编译的Hindle y - Milner类型检查的统一算法。
其次，编译器已越来越成为基于窗口的交互开发环境（interactive development environment，IDE ）的一部 分，它包括了编辑器、链接程序、调试程序以及项目管理程序。这样的IDE的标准并没有多少， 但是已沿着这一方向对标准的窗口环境进行开发了。
⑶ 编译过程分为哪几个阶段各阶段的遵循的原则、识别机构、使用的文法编译原理
编译原理中的遍概念
编译阶段也常常划分为两大步骤，分析步骤和综合步骤 分析步骤和综合步骤 分析步骤是指对源程序的分析 －线性分析(词法分析或扫描) －层次分析(语法分析) －语义分析 综合步骤是指后端的工作，为目标程序的生成而进行的综合
你分析过吗？若按照这种组合方式实现编译程序，可以设想，某一编译程序的前端加上相应不同的后 端则可以为不同的机器构成同一个源语言的编译程序。也可以设想，不同语言编译的前端生成同一种中间 语言，再使用一个共同的后端，则可为同一机器生成几个语言的编译程序。
一个编译过程可由一遍、两遍或多遍完成。所谓"遍"，也称作"趟"，是对源程序或其等价的中间语言程 序从头到尾扫视并完成规定任务的过程。每一遍扫视可完成上述一个阶段或多个阶段的工作。例如一遍可 以只完成词法分析工作；一遍完成词法分析和语法分析工作；甚至一遍完成整个编译工作。对于多遍的编 译程序，第一遍的输入是用户书写的源程序，最后一遍的输出是目标语言程序，其余是上一遍的输出为下 一遍的输入。
在实际的编译系统的设计中，编译的几个阶段的工作究竟应该怎样组合，即编译程序究竟分成几遍， 参考的因素主要是源语言和机器(目标机)的特征。比如源语言的结构直接影响编译的遍的划分；像 PL/1 或 ALGOL 68 那样的语言，允许名字的说明出现在名字的使用之后，那么在看到名字之前是不便为包含该名 字的表达式生成代码的，这种语言的编译程序至少分成两遍才容易生成代码。另外机器的情况，即编译程 序工作的环境也影响编译程序的遍数的划分。遍数多一点，整个编译程序的逻辑结构可能清晰些，但遍数 多即意味着增加读写中间文件的次数，势必消耗较多时间，一般会比一遍的编译要慢。
⑷ c语言源程序的编译过程包括哪三个阶段
编译：将源程序转换为扩展名为.obj的二进制代码
连接：将obj文件进行连接，加入库函数等生成可执行文件
运行：执行可执行文件，有错返回修改，无错结束
⑸ 编译器中都有哪些算法
词法/语法分析、程序分析与程序变换、代码生成、内存管理、虚拟机、函数式语言的实现与优化。。。每个话题都能出不止一本书。
用到的算法/数据结构多如牛毛：
各种树、图为主，其他如栈、队列、散列表、并查集。。。
贪心、回溯、动态规划、遗传算法、矩阵变换。。
在一个问题下很难回答好。。 先简单介绍一下和图相关的。
1. 和什么图打交道
CFG(Control Flow Graph)
控制流图是对程序中分支跳转关系的抽象，描述程序所有可能执行路径
节点是语句集合（basic block)；
每个basic block有唯一入口和出口；
如果A到B有边，表示A执行完后可能执行B
PDG(Program Dependence Graph)
PDG在编译器中用得不多，常见于软件工程/安全相关的应用（程序切片、安全信息流等）
SSA(Single Static Assignment)
SSA简化了很多数据流分析问题。
其他图
DJ Graph, Loop Nesting Forest, Program Structure Tree等等。
可参考：IR for Program Analysis。下面主要介绍CFG
2. CFG初步处理
CFG构造
dominator树生成
在CFG中，如果A是B的dominator，则从程序入口执行到B的任意路径一定经过A
控制依赖分析
根据dominator和post-dominator分析依赖关系。数据依赖、控制依赖信息在自动并行化中尤其重要（如果循环的每次迭代都没有依赖，那么可以并行处理）
控制流图化简
在复杂度相同的情况下，CFG的规模影响算法的效果。如果一个CFG仅通过如下变换能化简为一个节点，则它是可化简的：
如果节点n有唯一的前驱，那么将其和其前驱合并为一个节点
如果节点存在到自身的边，那么将该边删除
构造SSA
SSA可以由CFG构造。
3. CFG与数据流分析
下面才进入主题。。
一般的文献介绍DFA（Data flow analysis），都会用几个基础的分析为例：Constant Propagation，Range propagation，Avaliable expressions，Reaching Definition。而Reaching Definition的一个应用，就是大家喜闻乐见的“跳转到定义处”（真要做到“智能”跳转并不简单）
这部分涉及东西较多，一些算法也和”图“并不直接相关，不再展开。
PS，很多DFA问题可以用graph reachability统一建模，强烈推荐此文：
Program analysis via graph reachability
⑹ 最早的C语言编译器是什么做的
汇编。这真的是最早最早的。
准确的来说，这和编译器的开发有关，不用说太细，很麻烦怕你不懂。你现在假设第一个编译器是用会变写出来的，它的功能很简单，就是解释简单一种类似于C语言的高级语言，但是这种所谓的高级语言还没有完全拥有C语言的所有特性。只有比较简单核心功能，比如能把文本文件的高级语言转换成机器代码并且执行。
有了这个原型之后，就可以用这个编译器来解释简单C程序，就可以用C重写编写一个新的编译器，这样就有更多的C的功能。于是，从此之后就用现有的编译器解释更复杂的语言，用更复杂的语言写出更好的编译器，然后不断这样迭代。这确实是编译器的演变。
然后最后一个问题就是当一个新的CPU发明过后，怎么办，需要重写又从汇编开始写编译器吗？答案是不用。假设你有一个CPU A执行一些代码，你用汇编写了一个基础的C编译器，然后用C写出了更复杂的编译器，接受更复杂的C功能，然后不断循环演化。现在你有了CPU B，CPU B和CPU A执行两套完全不同的代码，那如何让CPU B的机器也可以变异C语言呢？因为现在A上面已经可以运行非常复杂的C语言程序了，所以你可以在A上面开发一个编译器把C语言程序转化为CPU B的执行代码。然后用这个程序，直接编译你的C语言编译器，再把这个程序转换到有B命令集的电脑上面，这样你就开发出了B电脑需要的C语言编译器。
所以除非你真的是活在非常早起的人类。否在现在的编译器基本上都利用这种原理直接编译已经用C语言或者其它高级语言写好的代码来产生新的编译器就行了。理论上可以只使用C语言来开发C的编译器，不过处于一些历史原因和底层效率等因素的考量，部分代码还是使用汇编来实现的。
我举得不过是一个例子，不一定是真实的C语言编译的进化，何况有这么多不同的C语言编译器，每一个的发展历史都有小的不同。但是基本上都是利用了这种编译器编译新的编译器的思想来实现了。而这样回溯回去，最早的编译器只能使用汇编来些。而其实最早的汇编语言的编译器就只能使用机器语言来写了。不过都是先处理简单的转换任务，有了这个核心功能过后，就可以写程序转换更复杂的语法。然后越来越复杂。就有了各种各样的高级语言编译器了。
⑺ c语言的编译过程是什么
c语言的编译过程如下：
1、预处理：预处理过程实际上是处理“#”的过程：#include包含的头文件直接拷贝到hello.c中；#define定义的宏定义进行替换，同时删除代码中没有的注释部分。2、编译：编译的过程实质上是将高级语言翻译成机器语言的过程。3、汇编：汇编器是将汇编代码转变成机器可以执行的命令，每一个汇编语句几乎都对应一条机器指令。汇编相对于编译过程比较简单，根据汇编指令和机器指令的对照表一一翻译即可。4、链接：就像hello.c中使用到了C标准库的东西“printf”，但是编译过程只是将源文件翻译成二进制文件而已，这个二进制文件还不能直接执行，还需要一个动作：将翻译成的二进制文件与需要用到的库绑定在一块。
补充：编译过程可分为6步：扫描（词法分析）、语法分析、语义分析、源代码优化、代码生成、目标代码优化。
⑻ 解释型语言和编译型语言的区别是什么
一、编译型
编译型语言：编译型语言在执行之前要先经过编译过程，编译成为一个可执行的机器语言的文件，比如exe。因为翻译只做一遍，以后都不需要翻译，所以执行效率高。
编译型语言的典型代表：C语言，C++。
编译型语言的优缺点：执行效率高，缺点是跨平台能力弱，不便调试。
二、解释型
解释型语言：解释性语言编写的程序不进行预先编译，以文本方式存储程序代码。执行时才翻译执行。程序每执行一次就要翻译一遍。
代表语言：python，JavaScript。
优缺点：跨平台能力强，易于调，执行速度慢。
编译型与解释型，两者各有利弊
前者由于程序执行速度快，同等条件下对系统要求较低，因此像开发操作系统、大型应用程序、数据库系统等时都采用它，像C/C++、Pascal/Object Pascal（Delphi）等都是编译语言。
而一些网页脚本、服务器脚本及辅助开发接口这样的对速度要求不高、对不同系统平台间的兼容性有一定要求的程序则通常使用解释性语言，如Java、JavaScript、VBScript、Perl、Python、Ruby、MATLAB等等。
⑼ C语言文件的编译与执行的四个阶段并分别描述
开发C程序有四个步骤：编辑、编译、连接和运行。
任何一个体系结构处理器上都可以使用C语言程序，只要该体系结构处理器有相应的C语言编译器和库，那么C源代码就可以编译并连接到目标二进制文件上运行。
1、预处理：导入源程序并保存（C文件）。
2、编译：将源程序转换为目标文件（Obj文件）。
3、链接：将目标文件生成为可执行文件（EXE文件）。
4、运行：执行，获取运行结果的EXE文件。
(9)编译语言的回溯扩展阅读：
将C语言代码分为程序的几个阶段：
1、首先，源代码文件测试。以及相关的头文件，比如stdio。H、由预处理器CPP预处理为．I文件。预编译的。文件不包含任何宏定义，因为所有宏都已展开，并且包含的文件已插入。我归档。
2、编译过程是对预处理文件进行词法分析、语法分析、语义分析和优化，生成相应的汇编代码文件。这个过程往往是整个程序的核心部分，也是最复杂的部分之一。
3、汇编程序不直接输出可执行文件，而是输出目标文件。汇编程序可以调用LD来生成可以运行的可执行程序。也就是说，您需要链接大量的文件才能获得“a.out”，即最终的可执行文件。
4、在链接过程中，需要重新调整其他目标文件中定义的函数调用指令，而其他目标文件中定义的变量也存在同样的问题。
⑽ 分别用回溯法和动态规划求0/1背包问题（C语言代码）
#include <stdio.h>
#include <malloc.h>
#include <windows.h>typedef struct goods
{
double *value; //价值
double *weight; //重量
char *select; //是否选中到方案
int num;//物品数量
double limitw; //限制重量
}GOODS;
double maxvalue,totalvalue;//方案最大价值,物品总价值
char *select1; //临时数组
void backpack(GOODS *g, int i, double tw, double tv)//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值
{
int k;
if (tw + g->weight[i] <= g->limitw)//将物品i包含在当前方案,且重量小于等于限制重量
{
select1[i] = 1; //选中第i个物品
if (i < g->num - 1) //若物品i不是最后一个物品
backpack(g, i + 1, tw + g->weight[i], tv); //递归调用,继续添加下一物品
else //若已到最后一个物品
{
for (k = 0; k < g->num; ++k) //将状态标志复制到option数组中
g->select[k] = select1[k];
maxvalue = tv; //保存当前方案的最大价值
}
}
select1[i] = 0; //取消物品i的选择状态
if (tv - g->value[i] > maxvalue)//若物品总价值减去物品i的价值还大于maxv方案中已有的价值,说明还可以继续向方案中添加物品
{
if (i < g->num - 1) //若物品i不是最后一个物品
backpack(g, i + 1, tw, tv - g->value[i]); //递归调用,继续加入下一物品
else //若已到最后一个物品
{
for (k = 0; k < g->num; ++k) //将状态标志复制到option数组中
g->select[k] = select1[k];
maxvalue = tv - g->value[i]; //保存当前方案的最大价值(从物品总价值中减去物品i的价值)
}
}
}
int main()
{
double sumweight;
GOODS g;
int i;
printf("背包最大重量:");
scanf("%lf",&g.limitw);
printf("可选物品数量:");
scanf("%d",&g.num);
if(!(g.value = (double *)malloc(sizeof(double)*g.num)))//分配内存保存物品价值
{
printf("内存分配失败\n");
exit(0);
}
if(!(g.weight = (double *)malloc(sizeof(double)*g.num)))//分配内存保存物品的重量
{
printf("内存分配失败\n");
exit(0);
}
if(!(g.select = (char *)malloc(sizeof(char)*g.num)))//分配内存保存物品的重量
{
printf("内存分配失败\n");
exit(0);
}
if(!(select1 = (char *)malloc(sizeof(char)*g.num)))//分配内存保存物品的重量
{
printf("内存分配失败\n");
exit(0);
}
totalvalue=0;
for (i = 0; i < g.num; i++)
{
printf("输入第%d号物品的重量和价值:",i + 1);
scanf("%lf%lf",&g.weight[i],&g.value[i]);
totalvalue+=g.value[i];//统计所有物品的价值总和
}
printf("\n背包最大能装的重量为:%.2f\n\n",g.limitw);
for (i = 0; i < g.num; i++)
printf("第%d号物品重:%.2f,价值:%.2f\n", i + 1, g.weight[i], g.value[i]);
for (i = 0; i < g.num; i++)//初始设各物品都没加入选择集
select1[i]=0;
maxvalue=0;//加入方案物品的总价值
backpack(&g,0,0.0,totalvalue); //第0号物品加入方案,总重量为0,所有物品价值为totalvalue
sumweight=0;
printf("\n可将以下物品装入背包,使背包装的物品价值最大:\n");
for (i = 0; i < g.num; ++i)
if (g.select[i])
{
printf("第%d号物品,重量:%.2f,价值:%.2f\n", i + 1, g.weight[i], g.value[i]);
sumweight+=g.weight[i];
}
printf("\n总重量为: %.2f,总价值为:%.2f\n", sumweight, maxvalue );
// getch();
return 0;
}