AcWing算法提高课-1.3.11二维费用的背包问题

这篇具有很好参考价值的文章主要介绍了AcWing算法提高课-1.3.11二维费用的背包问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

宣传一下算法提高课整理 <—

CSDN个人主页：更好的阅读体验 <—

AcWing算法提高课-1.3.11二维费用的背包问题

本题链接（AcWing）

点这里

题目描述

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

每件物品只能用一次。体积是 $v_i$ ，重量是 $m_i$ ，价值是 $w_i$ 。

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

输入格式

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

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

输出格式

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

数据范围

$\lt N \le 1000$
$\lt V, M \le 100$
$\lt v_i, m_i \le 100$
$\lt w_i \le 1000$

输入样例

输出样例：

思路

类比一维费用的01背包问题，二维费用的背包问题只是加入了一个花费。
因此，同样的，第二维的费用也是倒着循环，原理与普通一维背包相同。

$A C$ $C o d e$ :

$C + +$

#include <iostream>

using namespace std;

const int N = 110;

int n, V, M;
int f[N][N];

int main()
{
    cin >> n >> V >> M;
    
    for (int i = 1; i <= n; i ++ )
    {
    	int v, m, w;
    	cin >> v >> m >> w;
    	for (int j = V; j >= v; j -- )
    		for (int k = M; k >= m; k -- )
    			f[j][k] = max(f[j][k], f[j - v][k - m] + w);
	}
	
	printf("%d\n", f[V][M]);
    
    return 0; 
}