動态規劃法解決0-1背包問題

使用C語言實作的代碼如下所示

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

/*		   動态規劃法解決0-1背包問題(使用遞推公式進行資料生成)	    	*/

/* 定義背包的屬性 */
int package_total_contain;		//背包的容量
int package_max_value;			//在不超過背包容量的前提下，放入背包中的物品實作的最大價值

/* 定義物品的屬性 */
int goods_total_num;	  //總的物品的數量
int *pArrayGoodsWeight;	  //定義一個指針指向存放物品重量的數組
int *pArrayGoodsValue;	  //定義一個指針指向存放物品價值的數組
int *pArrayGoodsCount;	  //定義指針指向存放物品是否被選中的數組，選中就置為1，未選中就置為0，與物品一一對應,以此得出選取物品是哪些

/* 函數的聲明 */
void Init();
int GetMaxValue(int goods_total_num, int package_total_contain, int *pArrayGoodsWeight, int *pArrayGoodsValue, int *pArrayGoodsCount);
void DisPlay(int maxValue);

int main() 
{
	Init();

	int maxValue = GetMaxValue(goods_total_num, package_total_contain, pArrayGoodsWeight, pArrayGoodsValue, pArrayGoodsCount);

	//maxValue的值為-1時，表示使用者的輸入非法，程式直接結束
	if (maxValue == -1)
	{
		system("pause");
		return 0;
	}

	DisPlay(maxValue);

	system("pause");

	return 0;

}

/* 初始化函數，進行基本資料(背包的容量、物品的數量以及各個物品的重量與價值)的初始化 */
void Init() 
{
	printf("請輸入背包的的最大容量：");
	scanf("%d", &package_total_contain);

	printf("請輸入物品的數量：");
	scanf("%d", &goods_total_num);

	//背包的重量有0的這一列，是以配置設定的空間要加1
	pArrayGoodsWeight = (int *)malloc(sizeof (int) * (goods_total_num + 1));	
	for (int i = 1; i <= goods_total_num; i++) 
	{
		printf("請輸入第%d個物品的重量：",i);
		scanf("%d", pArrayGoodsWeight + i);
	}

	printf("\n");
	//物品的編号有0的這一行，是以配置設定的空間要加1
	pArrayGoodsValue = (int *)malloc(sizeof (int) * (goods_total_num + 1));
	for (int i = 1; i <= goods_total_num; i++) 
	{
		printf("請輸入第%d個物品的價值：",i);
		scanf("%d", pArrayGoodsValue + i);
	}

	//該數組與物品編号一一對應，選中就置為1，未選中就置為0，剛開始時全部初始化為0，也是從1開始存儲的
	pArrayGoodsCount = (int *)malloc(sizeof(int) * (goods_total_num + 1));
	for (int i = 1; i <= goods_total_num; i++) 
	{
		pArrayGoodsCount[i] = 0;
	}

	/* 進行使用者目前基本輸入資料的顯示，友善使用者的對比 */
	printf("\t\t\t\t您輸入的資料如下圖所示\n\n");

	printf("\t\t   物品序号\t\t   物品重量\t\t   物品價值\n");

	for (int i = 1; i <= goods_total_num; i++)
	{	
		printf("\t\t%8d\t\t%8d\t\t%8d\n", i, pArrayGoodsWeight[i], pArrayGoodsValue[i]);
	}
	printf("\n");
}

/*
	該函數實作生成最大價值表以及得出實作的最大價值和物品選擇序列
	@param  goods_total_num			物品的總數量
	@param  package_total_contain   背包的最大容量
	@param  pArrayGoodsWeight		指向儲存物品重量數組的首位址的指針變量
	@param  pArrayGoodsValue	    指向儲存物品價值數組的首位址的指針變量
	@param  pArrayGoodsCount        指向儲存物品是否被選中數組的首位址的指針變量
**/
int GetMaxValue(int goods_total_num, int package_total_contain, int *pArrayGoodsWeight, int *pArrayGoodsValue, int *pArrayGoodsCount) {

	//表示使用者輸入了背包容量或物品數量非法時，直接傳回-1，将不執行生成最大價值表的程式
	if (goods_total_num <= 0 || package_total_contain <= 0)
	{
		return -1;
	}

	//表格的行數等于物品的數量，每個物品對應一行資料，由于有一行全為0，是以要加上1
	int row_num = goods_total_num + 1;

	//表格的列是按照背包重量從1開始進行遞增，由于有背包重量是0的那一列，是以列數等于背包重量加1
	int col_num = package_total_contain + 1;

	//建立一個value指針變量，存放行的指針數組資訊
	int ** value = (int **)malloc(sizeof (int *));

	//建立行數組，并将首位址發送給value指針
	value = (int **)malloc(sizeof(int *) * row_num);

	//建立列數組，并将首位址發送給行指針數組
	for (int i = 0; i < col_num; i++) 
	{
		value[i] = (int *)malloc(sizeof(int) * col_num);
	}

	//進行初始化操作，初始化第0行,設定該行數值為0
	for (int i = 0; i < col_num; i++)
	{
		value[0][i] = 0;
	}

	//進行初始化操作，初始化第0列,設定該行數值為0
	for (int i = 0; i < row_num; i++) 
	{
		value[i][0] = 0;
	}

	//進行計算,算出每一行每一列的最大價值,i表示物品編号，j表示背包容量
	for (int i = 1; i < row_num; i++) 
	{
		for (int j = 1; j < col_num; j++) 
		{
			//如果是該中情況，表明此時背包已經裝不下了，該件物品将不會放入背包
			value[i][j] = value[i - 1][j];

			//如果物品能裝入背包，此時的最大價值是該temp值
			int tempValue = value[i - 1][j - pArrayGoodsWeight[i]] + pArrayGoodsValue[i];

			//當物品能夠放入背包中，并且放入的價值大于不放入的價值時，改變此時的最大價值
			if (pArrayGoodsWeight[i] <= j && tempValue > value[i][j])
			{
				value[i][j] = tempValue;
			}
		}
	}
	
	//最大價值表的列的下标最大值是col_num - 1
	int j = col_num - 1;

	/* 逆推法求出裝入的物品,從最右下角開始往前推 */
	for (int i = row_num - 1; i > 0; i--) 
	{
		//如果後面的價值大于前一個，表示該物品被選進了背包
		if (value[i][j] > value[i - 1][j]) 
		{
			//設定該物品被選中，作為一種标記,設定其值為1，以便知道哪些被選中了
			pArrayGoodsCount[i] = 1;

			//将該物品的重量從總的重量中減去
			j -= pArrayGoodsWeight[i];
		}
	}

	//記錄最大的價值
	int max_value = value[row_num - 1][col_num - 1];

	printf("\n");		//輸出一個換行符

	printf("\t最大價值表如下圖所示\n");

	printf("   ");		//輸出3個空格使資料對齊

	for (int i = 0; i < col_num; i++)
	{
		printf("%3d", i);	//進行列标題的輸出，表示背包的重量
	}

	printf("\n");		//輸出一個換行符

	//進行目前每一個value[i][j]值的列印,行數等于物品數量加1，縱向數量等于背包最大容量加1
	for (int i = 0; i <= goods_total_num; i++)
	{
		printf("%3d", i);	

		for (int j = 0; j <= package_total_contain; j++)
		{
			printf("%3d", value[i][j]);
		}

		printf("\n");	//每輸出一行進行一次換行操作
	}

	printf("\n");		//輸出一個換行符


	return max_value;
}

/* 該函數實作最終結果的顯示 */
void DisPlay(int maxValue) 
{
	printf("實作的最大價值是：%d\n", maxValue);

	printf("選取的物品序列是：");

	for (int i = 1; i <= goods_total_num; i++) 
	{
		if (pArrayGoodsCount[i] == 1)
		{
			printf("%d ", i);
		}
	}
	printf("\n");	
}
           

運作的結果如下圖所示