首页 > 代码库 > 多重背包

多重背包

//多重背包void WKnapsack4(int *value, int* v, int *Num, int n, int V){   	int d[100][100];	memset(d, 0, sizeof(int)* 100*100);	bool  visit[100][100];	memset(visit, 0, sizeof(bool)* 100 * 100);	int  times[100][100];	memset(times, 0, sizeof(int)* 100 * 100);	for (int i = 0; i < n; i++)	{		for (int j = v[i]; j <= V; j++) 		{			for (int k = 0; k <= Num[i]; k++)			{				if (i == 0)				{					d[i][j] = 0;				}				else if(j >= k*v[i])				{					if (d[i][j] < d[i - 1][j - k*v[i]] + k*value[i])					{						visit[i][j] = true;						times[i][j] = k;					}					d[i][j] = max(d[i][j], d[i - 1][j - k*v[i]] + k*value[i]); 				}			}			}	}	printf("%d ", d[n-1][V]);	//多重背包,打印 	printf("打印路径:\n");	for (int i = n - 1, j = V; i >= 0 && j>0; i--)	{		if (visit[i][j]) //		{			printf("value:%d  num:%d\n",value[i], times[i][j]);			j = j - v[i];		}	}}

  

多重背包