C++背包问题详解2-创新互联

• 多重背包
• • 例题：Acwing 4.多重背包问题1
  • • 思路
    • 代码
  • 例题：Acwing 5.多重背包2
  • • 思路
    • 代码

题目描述：

有 N N N 种物品和一个容量是 V V V 的背包。

第 i i i 种物品最多有 s i si si 件，每件体积是 v i vi vi，价值是 w i wi wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和大。
输出大价值。

输入格式:
第一行两个整数， N N N， V V V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N N N 行，每行三个整数 v i vi vi， w i wi wi， s i si si，用空格隔开，分别表示第 i i i 种物品的体积、价值和数量。

输出格式:
输出一个整数，表示大价值。

数据范围:
0 < N , V ≤ 100 0 0 < v i , w i , s i ≤ 100 0

输入样例:

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

本题的题目描述一看就是一道典型的背包题目

（如果对背包类题目不了解的可以先去读一下C++背包详解）

因为题目条件里给出了物品的数量

会发现这并不是01背包或完全背包

而是一种新的类型—多重背包

即每种物品可以取有限次

其实对于大多数动态规划类型的题目，

都可以通过样例从后往前推状态转移方程

背包容积： V = 5 V=5 V=5

依旧可以使用从后往前举例的做法

设 f [ i ] [ j ] f[i][j] f[i][j] 表示前 i i i 个物品用 j j j 的体积所获得的大价值

因为只需要调用本行和上一行的值，所以可以直接将二维压成一维，减少空间

即 f [ j ] f[j] f[j]

对于第 4 4 4 个物品来说，

如果取第 4 4 4 个物品：

那么体积减少 4 4 4，价值增加 5 5 5，但仍旧需要判断物品是否用光
（ f [ j − 4 ] f[j-4] f[j−4] ）

如果不取第 4 4 4 个物品，那么体积不变( f [ j ] f[j] f[j] )

可得状态转移方程： f [ j ] = m a x ( f [ j ] , f [ j − v [ i ] ] + w [ i ] ) f[j]=max(f[j],f[j-v[i]]+w[i]) f[j]=max(f[j],f[j−v[i]]+w[i])

这时，还有一个问题需要考虑：物品数量怎么处理？

这时我们就需要有一种思路

将多重背包拆分成01背包

即把多个相同物品看做一个个不同物品（实质是相同的）

这样只需要在外面循环一遍数量就可以了

#includeusing namespace std;

int n,V;
int v[105],w[105],s[105];
int f[105]

int main()
{cin>>n>>V;
    for(int i=1;i<=n;i++)
    {cin>>v[i]>>w[i]>>s[i];
    }
    for(int i=1;i<=n;i++)
    {for(int k=1;k<=s[i];k++)
        {for(int j=V;j>=v[i];j--)
            {f[j]=max(f[j],f[j-v[i]]+w[i]);
            }
        }
    }
    cout<

#includeusing namespace std;

int n,V;
int v[1005],w[1005],s[1005];
int f[2005];

int main()
{cin>>n>>V;
	for(int i=1;i<=n;i++)
	{cin>>v[i]>>w[i]>>s[i];
	}
	for(int i=1;i<=n;i++)
	{if(v[i]*s[i]>=V)
		{	for(int j=v[i];j<=V;j++)
			{		f[j]=max(f[j],f[j-v[i]]+w[i]);
			}
		}
		else
		{	for(int k=1;s[i]>0;k*=2)
			{		int x=min(k,s[i]);
				for(int j=v;j>=x*v[i];j--)
				{f[j]=max(f[j],f[j-x*v[i]]+x*w[i]);
				}
				s1[i]-=x;
			}
		}
	}
	cout<