01背包.动态规划.c语言实现

01背包.动态规划.c语言实现

二维dp数组01背包

确定dp数组以及下标的含义

 使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少

      2.递推公式：dp[i][j]=dp[i-1][j-weight]+value[i]   dp[i][j]=dp[i-1][j]

     3.数组初始化：dp[100][100]={0};

for(j=BagSize;j>=weight[0];j--)//第一个物品重量
	{
		//dp[0][j]=dp[0][j - weight[0]]+value[0];//第一列都为一个数
		dp[0][j]=value[0];//第一个物品的价值
	}

    4.遍历数组：

for(j=1;jdp[j-1][k])
				    dp[j][k]=dp[j-1][k-weight[j]]+value[j];
				else
					dp[j][k]=dp[j-1][k];
			//当k=weight[j]时dp[j-1][k-weight[j]]==0
		}

  5.打印数组

for ( j= 0; j < i; j++) 
	{
		for ( k = 0; k <=BagSize; k++)
		{
			printf("%d  ",dp[j][k]);
		}
		printf("n");
	}

 6.总代码

#include
int main()
{   //dp[i][j]是物品放入任意容量为j的背包中的最大价值
	int BagSize,weight[100],value[100],dp[100][100]={0};
	int i=0,j,k,t,m;
	scanf("%d",&BagSize);
	while(scanf("%d %d",&weight[i],&value[i])!=EOF)
	{
		i++;
	}
	//初始化
	for(j=BagSize;j>=weight[0];j--)//第一个物品重量
	{
		//dp[0][j]=dp[0][j - weight[0]]+value[0];//第一列都为一个数
		dp[0][j]=value[0];//第一个物品的价值
	}

	//dp[i][0]=0;
	
	//遍历数组
	for(j=1;jdp[j-1][k])
				    dp[j][k]=dp[j-1][k-weight[j]]+value[j];
				else
					dp[j][k]=dp[j-1][k];
			//当k=weight[j]时dp[j-1][k-weight[j]]==0
		}
		printf("%d",dp[i-1][BagSize]);
		printf("n");
		//动态规划表的输出
	for ( j= 0; j < i; j++) 
	{
		for ( k = 0; k <=BagSize; k++)
		{
			printf("%d  ",dp[j][k]);
		}
		printf("n");
	}

		return 0;
}