宣传一下算法提高课整理 <—
CSDN个人主页：更好的阅读体验 <—
本题链接（AcWing）
点这里
题目描述
有 N N N 件物品和一个容量是 V V V 的背包，背包能承受的最大重量是 M M M。
每件物品只能用一次。体积是 v i v_i vi，重量是 m i m_i mi，价值是 w i w_i wi。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。
输入格式
第一行三个整数， N , V , M N,V, M N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。
接下来有 N N N 行，每行三个整数 v i , m i , w i v_i, m_i, w_i vi,mi,wi，用空格隔开，分别表示第 i i i 件物品的体积、重量和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0 < N ≤ 1000 0 \lt N \le 1000 0<N≤1000
0 < V , M ≤ 100 0 \lt V, M \le 100 0<V,M≤100
0 < v i , m i ≤ 100 0 \lt v_i, m_i \le 100 0<vi,mi≤100
0 < w i ≤ 1000 0 \lt w_i \le 1000 0<wi≤1000
输入样例
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
输出样例：
8
思路
类比一维费用的01背包问题，二维费用的背包问题只是加入了一个花费。
因此，同样的，第二维的费用也是倒着循环，原理与普通一维背包相同。
A C AC AC C o d e Code Code:
C + + C++ 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;
}
最后，如果觉得对您有帮助的话，点个赞再走吧！
