我们的节日儿童画:帮忙做c作业,送出全部积分!

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, Typep & value,
Typew w1[ ], Typep v1[ ] ){
TOT = total;
n = num;
Y = value;
w = new Typew[n+1];
v = new Typep[n+1];
for (int j=1;j <= n; j++) { w[j]=w1[j];v[j]=v1[j];}
}
template
Typep knap :: f( Typew t, int i ) {
// remnant 背包的剩余重量.i 当前已经考察的物品件数.
Typep amount = 0;
++i;
while( i <= n && w[i] <= t ) {
t -= w[i];
amount += v[i];
++i;
} // 按照物品的单价的递减序装填背包.
if ( i <= n ) amount += t * v[i]/w[i];
return amount;
} // 得到背包的剩余重量所能够达到的最大的价值上界.
template
void knapsack( knap & ks ) {
ks.Y = 0; // Y 记录在算法执行过程中得到一种填充方案时的背包价值,初值为0.
stack s; // 记录当前重量,价值,已考虑的物品件数的堆栈
WVM x;
x.weight = 0.0; x.val = 0.0; x.m = 1; // 图9.16 所示根结点的右儿子
s.push(x);
x.weight = ks.w[1]; x.val = ks.v[1]; x.m = 1; // 图9.16 所示根结点的左儿子
s.push(x);
while ( s.empty() == false )
{ x = s.top();
if ( x.m == ks.n ) { if ( x.val > ks.Y ) ks.Y = x.val;
// 当前一种填充方案的背包价值,可用
// 作削减结点的价值约束.
s.pop();
}
else if ( x.val + ks.f( ks.TOT - x.weight, x.m) > ks.Y )
{ x.m += 1;
//结点的右儿子的重量价值不变,考察物品的件数多了1件.
s.pop( ); s.push(x); // 父结点弹出,其右儿子的各项数据进栈.
if ( ( x.weight + ks.w[x.m]) <= ks.TOT )
// 若下一件物品重量和原背包重量之和小于重量
// 限制 TOT, 则原结点的左儿子可生成.
{ x.weight += ks.w[x.m]; //父结点的左儿子的重量.
x.val += ks.v[x.m]; //父结点的左儿子的价值.
s.push( x ); //左儿子的各项数据进栈.
}
}
else s.pop( ); // 该结点不可能产生更好的结果,弹出.
}
cout << "The value of best knapsack filling solution is" << ks.Y << "!" << endl;
}

2-------------------------------------------
*本程序在输入多项式时候，先输入低次系数，在输入高次*/
/*write by elva6401*/
#include <stdio.h>
int main()
{
int m,n,*k;
int *a,*b,*c;
int i;
printf("Enter the number of m,n\n");
scanf("%d%d",&m,&n);
m++;
n++;
a=(int *)malloc(m*sizeof(int));
b=(int *)malloc(n*sizeof(int));
c=(int *)malloc((m+n-1)*sizeof(int));
printf("Enter the a\n");
for(i=0;i<m;i++)
scanf("%d",&a[i]);
printf("\nThe a is:\n");
for(i=0;i<m;i++)
{
if (i!=0) printf("+");
printf("%dx^%d",a[i],i);
}
printf("\nEnter the b\n");
for(i=0;i<n;i++)
scanf("%d",&b[n-i-1]);
printf("The b is:\n");
for(i=0;i<n;i++)
{
if (i!=0) printf("+");
printf("%dx^%d",b[i],i);
}
muity(a,m,b,n,c,k);
printf("\nThe c is:\n");
for(i=0;i<*k-1;i++)
{
if (i!=0) printf("+");
printf("%dx^%d",c[i],i);
}
getch();
}
int muity(int a[],int m,int b[],int n,int c[],int *k)
{
int i,j;
* k=m+n;
for(i=0;i<m+n-1;i++)
c[i]=0;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
c[i+j]=a[i]*b[j]+c[i+j];
}

3------------------------------

template<class T>
void Perm(T list[], int k, int m)
{
/ /生成list [k：m ]的所有排列方式
int i;
if (k == m)
{//输出一个排列方式
for (i = 0; i <= m; i++)
{
cout << list [i];
cout << endl;
}
}

else // list[k：m ]有多个排列方式
{
// 递归地产生这些排列方式
for (i=k; i <= m; i++)
{
Swap (list[k], list[i]);
Perm (list, k+1, m);
Swap (list [k], list [i]);
}
}
}