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

一：问题

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

和第三篇一样，我们来求出最大价值的个数。

二：分析理解

我们设置num[ i ][ j ]二维数组来表示dp[ i ][ j ]的方案数。

1.dp[ i ][ j ] == dp[ i-1 ][ j ]且dp[ i ][ j ] != dp[ i ][ j-Ci ] + Wi 的时候，num[ i ][ j ] = num[ i-1 ][ j ] ；

2.dp[ i ][ j ] != dp[ i-1 ][ j ]且dp[ i ][ j ] == dp[ i ][ j-Ci ] + Wi 的时候，num[ i ][ j ] = num[ i-1 ][ j-Ci ] ；

3.dp[ i ][ j ] == dp[ i-1 ][ j ]且dp[ i ][ j ] == dp[ i ][ j-Ci ] + Wi 的时候，num[ i ][ j ] = num[ i-1 ][ j ]  + num[ i-1 ][ j-Ci ]；

这里可以压缩下num[ i ][ j ]，压缩成num[ j ]，同dp[ i ][ j ]压缩成dp[ j ]一样。

#include
   
      #include
    
       using namespace std;#define N 6#define V 10                         //背包容量int w[N + 1] = { 0,1,3,1,4,40,5 };    //6个物品的价值,第一个0除外int v[N + 1] = { 0,4,6,5,1,10,7 };   //6个物品的体积,第一个0除外int dp[V + 5];int num[V + 5];int main(){	fill(num, num + V + 5, 1);	for (int i = 1; i <= N; i++)	{		for (int j = v[i]; j <= V; j++)		{			if (dp[j] < dp[j - v[i]] + w[i])			{				dp[j] = dp[j - v[i]] + w[i];				num[j] = num[j - v[i]];			}			else if (dp[j] == dp[j - v[i]] + w[i])				num[j] += num[j - v[i]];		}	}	printf("最大价值是：%d\n", dp[V]);	printf("此时背包的最大价值个数是：%d\n", num[V]);	return 0;}
    
   

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

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