main.cpp

我做的一些C语言练习题,里面一共有76道题目,主要用到一些计算机常用的算法,如:递归,分治,动态规划,回溯法,AO算法等,除此之外还用到比较多的数学知识,我做了一部分,还有一些暂时还没做出来,大家也帮

/******************************************************************************
19. (背包问题) 有 N 件物品 d1，......dN，每件物品重量为 W1，..., WN
 (Wi > 0)， 每件物品价值为 V1，......VN (Vi>0)。用这N件物品的某个子集
 填空背包，使得所取物品的总重量<=TOTAL，并设法使得背包中物品的价值尽可
 能高。

  输入:N件物品d1....dn,每件重量为w1...wn,每件价值v1...vn;
  输出:N见物品的子集{di | 1 =< i <= n}
  过程:动态规划算法(递推)
  假设H[d,w]是代表含有第d件物品且总重量为w的物品总价值;得到递推式
  H[d,w] = 0 其中(d=0 || w=0) 表示没有物品或重量时,总价值为0
  H[d,w] = H[d-1,w] (w<wi)
  H[d,w] = max{ H[d-1,w-wi]+vi , H[d-1,w] } 其中(wi=<w<=TOTAL,d>=1)
 ******************************************************************************/

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <time.h>

static int N; // 物品的总数
static int TOTAL; // 物品的最大重量限制
static int *wi; //物品重量
static int *vi; //物品价值

//显示数据
void ShowData()
{
	int i;

	printf("               数据              \n");
	printf("---------------------------------\n");
	printf("%s%10s%10s\n","序号","重量","价值");
	printf("---------------------------------\n");
	for(i=0; i<N; i++)
		printf("%2d%10d%10d\n",i,wi[i],vi[i]);
	printf("---------------------------------\n");
	printf("\n");
}

//显示结果
void ShowResult(int **P, int **S)
{
	int d,w = TOTAL;
	printf("               结果              \n");
	printf("---------------------------------\n");
	printf("%s%10s%10s\n","序号","重量","价值");
	printf("---------------------------------\n");
	for(d=N; d>=1; d--)
	{
		if(S[d][w])
		{
			printf("%2d%10d%10d\n",d-1,wi[d-1],vi[d-1]);
		}
		w = P[d][w];
	}
	printf("---------------------------------\n");
	printf("\n");
}

void main()
{
	int i;
	int d,w;
	int **H;
	int **P;
	int **S;

	printf("请输入物品总数N和物品最大重量限制TOTAL:\n");
	scanf("%d%d",&N,&TOTAL);

	//申请空间
	wi = (int*)malloc(N*sizeof(int));//重量
	vi = (int*)malloc(N*sizeof(int));//价值
	H = (int**)malloc((N+1)*sizeof(int*));//解价值数组
	//..............................................
	P = (int**)malloc((N+1)*sizeof(int*));//保存解路径
	S = (int**)malloc((N+1)*sizeof(int*));//该序号的物品是否有选中
	//..............................................

	for(i=0; i<=N; i++)
		H[i] = (int*)malloc((TOTAL+1)*sizeof(int));
	//..............................................
	for(i=0; i<=N; i++)
		P[i] = (int*)malloc((TOTAL+1)*sizeof(int));
	for(i=0; i<=N; i++)
		S[i] = (int*)malloc((TOTAL+1)*sizeof(int));
	//...............................................

	srand(time(NULL));
	for(i=0; i<N; i++)
		wi[i] = rand()%(TOTAL/2)+1;
	for(i=0; i<N; i++)
		vi[i] = rand()%10+1;
	
	ShowData();
	//初始化
	for(d=0; d<=N; d++)
	{
		for(w=0; w<=TOTAL; w++)
		{
			if(d==0 || w==0)
				H[d][w] = 0;
			else if(w<wi[d-1])
			{
				H[d][w] = H[d-1][w];
				//...........................
				P[d][w] = w;
				S[d][w] = 0;
				//...........................
			}
			else
			{
				H[d][w] = H[d-1][w-wi[d-1]]+vi[d-1];
				//.................................
				P[d][w] = w-wi[d-1];
				S[d][w] = 1;
				//.................................
				if(H[d][w] < H[d-1][w])
				{
					H[d][w] = H[d-1][w];
					//............................
					P[d][w] = w;
					S[d][w] = 0;
					//............................
				}
			}
		}
	}
	//显示结果
	ShowResult(P,S);
	printf("%d\n",H[d-1][w-1]);

	//释放空间
	free(wi);
	free(vi);
	for(i=0; i<=N; i++)
		free(H[i]);
	free(H);
	for(i=0; i<=N; i++)
		free(P[i]);
	free(P);
	for(i=0; i<=N; i++)
		free(S[i]);
	free(S);

}