背包系列第三篇----01背包（求解最大价值的个数）

59 阅读 0 评论 39 点赞

我是靠谱客的博主香蕉鞋垫，最近开发中收集的这篇文章主要介绍背包系列第三篇----01背包（求解最大价值的个数），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一：问题

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

什么叫最大价值的个数？

当我们求出一个背包问题的最大价值时，这个最大价值是固定的，但是背包里的物品可能不一样。

二：分析理解

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

我们初始化num[ i ][ j ]为1，因为对每个F[i][j]至少应该有一种方案，即前i件物品中选取若干件物品放入剩余空间为j的背包使其价值最大的方案数至少为1，因为F[i][j]一定存在。

如何求解num[ i ][ j ]需要分三种情况。

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

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

3.dp[ i ][ j ] == dp[ i-1 ][ j ]且dp[ i ][ j ] == dp[ i-1 ][ 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<iostream>
#include<algorithm>
using namespace std;
#define N 6
#define V 10
//背包容量
int w[N + 1] = { 0,5,3,1,4,6,5 };
//6个物品的价值,第一个0除外
int v[N + 1] = { 0,7,6,5,1,19,7 };
//6个物品的体积,第一个0除外
int dp[V + 5];
int num[V + 5];
int main()
{
fill(num, num + V + 5, 1);//初始设置为1
for (int i = 1; i <= N; i++)
{
for (int j = V; j >= v[i]; 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("最大价值是：%dn", dp[V]);
printf("此时背包的最大价值个数是：%dn", num[V]);
return 0;
}

四：数据测试