AcWing 8. 二维费用的背包问题
原题链接
中等
作者:
总有刁民想害朕
,
2020-03-11 22:11:34
,
所有人可见
,
阅读 580
本题属于多维费用问题,只需要在一维的基础上加一维即可,枚举顺序和一维一样,这类问题还有多维体积问题,思路基本一样
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
struct thing{
int v, w, p;
};
vector<thing> things;
int dp[N][N];
int n, v, m;
int main(){
cin >> n >> v >> m;
for(int i = 0;i < n;++i){
int v, w, p;
cin >> v >> w >> p;
things.push_back({v, w, p});
}
for(int i = 0;i < things.size();++i)
for(int j = v;j >= things[i].v;--j)
for(int k = m;k >= things[i].w;--k)
dp[j][k] = max(dp[j][k], dp[j-things[i].v][k-things[i].w] + things[i].p);
cout << dp[v][m];
}