mfknapsack.cpp

此文件夹中共包括十二个小程序 AVL创建平衡二叉树,通过加入一个个的结点创建,并实现了平衡二叉树中的结点删除 Boyer_Moore算法的串模式匹配 Horspool算法的串模式匹配 Grap

//动态规划解背包问题

#include <stdio.h>
#include <stdlib.h>
#define N 10
int limitw;  //限制的总重量
int totv;   //全部物品的总价值
int maxv;
int option[N];  //option[]数组存放物品选择情况,值为1表示选择该物品
int V[N][N];      //辅助数组
struct
{
	int weight;
	int value;
}a[N];
int n; //共n件物品

int find(int n,int tw)//物品总数n,总承重量tw,返回值为最大价值
{
	int value,maxvalue;
	int i,j;
	for(i=0;i<=n;i++) //初始化数组V，令第0行和第0列元素值全为0
		V[i][0]=0;
	for(j=0;j<=tw;j++)		
		V[0][j]=0;		
	
	for(i=1;i<=n;i++)
		for(j=1;j<=tw;j++)
		{
			if(j<a[i].weight) //承重量小于物品重量时		
				V[i][j]=V[i-1][j];	
			else 
			{				
				value=V[i-1][j-a[i].weight]+a[i].value;//加入物品i后的价值放入value中
				if(V[i-1][j]>value)
					maxvalue=V[i-1][j];
				else
					maxvalue=value;	
				
				V[i][j]=maxvalue;
			}
		}

	for(i=n;i>=0;i--)//修改option数组的值
		for(j=tw;j>=0;j--){	
			
				if(V[i-1][j-a[i].weight]+a[i].value==V[i][j])
					option[i-1]=1;//选择物品i时，option的值设为1
				else
					option[i-1]=0;
				j=j-a[i].weight;//修改j的值
			}	
	
		return maxvalue;
}

void main()
{
	int k;	
    int n=4;
    a[1].weight=2;  a[1].value=12;
    a[2].weight=1;  a[2].value=10;
    a[3].weight=3;  a[3].value=20;
    a[4].weight=2;  a[4].value=15;

	printf("物品种数为4:\n ");
	for(k=1; k<=n; k++)
		printf("第%d种物品:重量%d,价值%d\n ",k,a[k].weight,a[k].value);
	printf("\n");

	printf("背包所能承受的总重量为5\n");
	limitw=5;       //limitw为背包所能承受的总重量

	maxv=0; //存放方案中物品的最大价值
	for(k=0;k<n;k++) //初始化option[]数组元素均为0
		option[k]=0;

	maxv=find(n,limitw); //查找最佳方案

	printf("最佳装填方案是: \n");
	for(k=0;k<n;k++)
		if(option[k])  //若option[k]=1,则表明该物品在最佳方案中
			printf("  第%d种物品\n",k+1);

	printf("总价值=%d\n",maxv);

	system("PAUSE");
}