UC知道帮忙做c作业,送出全部积分!
来源：百度知道 编辑：UC知道 时间：2024/05/10 11:28:14
1．(0-1背包问题) 有 N 件物品 d1，......dN，每件物品重量为 W1，..., WN (Wi >0)，每件物品价值为 V1，......VN (Vi>0)。从这N件物品中选部分物品装入背包，使背包内物品的总重量不超过背包的容量TOTAL，并使背包中物品的总价值最高。（采用递归回溯求解）
2.（多项式乘法）编写计算两个多项式相乘P(x)Q(x)=R(x)的函数：
void muity(float a[],int m,float b[],int n,float c[]，int *k);
其中数组a[],b[],c[]分别存放三个多项式的系数，m,n,k分别是多项式P(x)、Q(x)、R(x)的次数，通过形参与实参的结合返回c[],k的值。
3．（全部排列）给定n个不同的数字（n<10），利用递归方式编程求这n个数字的全部可能的排列。
要求包括:算法简介，源程序，对主要变量和重要语句的注释，运行结果的说明
1------------------------------
背包问题是一个非常有名的问题.可以这样叙述如下.假设有 n 件物品,记为 d1,d2,d3,…… dn.对于每一种物品di (1== v3/w3>= v4/w4>= v5/w5,这样算法再考虑将物品放入背包时,首先考虑的是取单价尽可能高的物品,以使背包的价值尽量大.在以后的程序 8.1 中,也遵循这样的惯例.
程序 8.1 背包问题的类 knap 的定义及背包问题的解法
typedef struct wvm {
float weight; // 当前的重量
float val; // 当前的价值
int m; // 当前考察的物品件数.
}WVM; // 解答空间树中的结点类型.
#include
#include
using namespace std;
template
class knap {
friend void knapsack( knap & );
public:
knap( const Typew total, const int num, Typep & value, Typew w1[ ], Typep v1[ ] );
~knap( ){ delete [ ]w; delete []v;}
private:
Typep f( Typew remnant,int i ); // 从i+1 物品开始计算,背包的剩余重量 remnant
// 可以达到的价值的最大上界.
Typew TOT; // 背包的重量限制,如上例为 TOT 为37.
int n; // 给定的物品件数,如上例为 n 为 5.
Typew * w; // n 件物品的重量数组.
Typep * v; // n 件物品的价值数组.
Typep Y; // 得到的背包最优价值,初值为0.
};
template
knap :: knap( const Typew total, const int num, Type