二维0-1背包问题

题目来源：8. 二维费用的背包问题 - AcWing题库

题目：

有?N?件物品和一个容量是?V 的背包，背包能承受的最大重量是?M。

每件物品只能用一次。体积是?vi，重量是?mi，价值是?wi。

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

输入格式

第一行三个整数，N,V,M用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有?N 行，每行三个整数?vi,mi,wi用空格隔开，分别表示第?i?件物品的体积、重量和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N≤1000
0<V,M≤100
0<vi,mi≤100
0<wi≤1000

输入样例

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

输出样例：

8

题目解析：二维0-1背包问题和一维0-1背包问题（见博客：01背包问题-CSDN博客）解法一样，只不过将数组f[i]改为f[i][j],加一重循环，此刻表示在i体积下j质量下的最大价值。

上代码：

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=110; 
int n,v,m;//n数量,v体积,m质量 
int f[N][N];//f[i][j]表示在i体积j质量下的最大价值 
int main()
{
	cin>>n>>v>>m;
	for(int i=1;i<=n;i++)
	{
		int vv,mm,ww;
		cin>>vv>>mm>>ww;
		//二维0-1背包问题，从大到小遍历 
		for(int j=v;j>=vv;j--)//遍历体积 
			for(int k=m;k>=mm;k--)//遍历质量 
			f[j][k]=max(f[j][k],f[j-vv][k-mm]+ww);
	}
	cout<<f[v][m];
	return 0;
}