本文共 929 字，大约阅读时间需要 3 分钟。

一：问题

完全背包问题描述：一个容量为V的背包。现在有N种物品，每种物品有无数个，每种物品的体积是C1，C2，…，Cn，对应的每种的价值是W₁,W₂，…，W_n.。试问，在不超过背包容量的情况下，物品装入背包的最大价值？

在此基础上，如何求出背包内的物品？

二：分析理解

和背包系列的第二篇相似，需要设置一个path[ ][ ]保存路径。

三：代码

#include
   
      #include
    
       using namespace std;#define N 6#define V 10                         //背包容量int w[N + 1] = { 0,2,3,1,4,6,5 };    //6个物品的价值,第一个0除外int v[N + 1] = { 0,5,6,5,1,19,7 };   //6个物品的体积,第一个0除外int dp[V + 5];int path[N + 5][V + 5];              //初始置0int main(){	for (int i = 1; i <= N; i++)	{		for (int j = v[i]; j <= V; j++)		{			path[i][j] = 0;			if (dp[j] < dp[j - v[i]] + w[i])			{				dp[j] = dp[j - v[i]] + w[i];				path[i][j] = 1;			}		}	}				printf("最大价值是：%d\n", dp[V]);	printf("此时背包里的物品价值分别是：");	int i = N;//N个物品  	int j = V;//背包容量是V  	while (i > 0 && j > 0)	{		if (path[i][j] == 1)		{			printf("%d ", w[i]);			j -= v[i];		}		else               //注意此处，和第二篇的不同之处			i--;	}	printf("\n");	return 0;}
    
   

返回背包系列目录--->

转载地址：https://blog.csdn.net/LaoJiu_/article/details/51285830 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！