二费背包问题
典型例题
https://www.luogu.com.cn/problem/P1855
#include<bits/stdc++.h> #define MAXVAL 100005 using namespace std; struct good { int p; int w; int v; good():p(0),w(0),v(0){}; }; bool cmp(const good& a, const good& b) { if(a.v != b.v) return a.v>b.v; else return a.p<b.p; } vector<good> goods(100005); int dp[105][10005]; int main(int argc, char const *argv[]) { int n, m, K; cin>>n>>m>>K; for(int i = 1; i<=n; ++i) //下标1开始 { cin>>goods[i].p>>goods[i].w>>goods[i].v; } sort(goods.begin(),goods.end(),cmp); //坑点,习惯了用下标1开始,这里排序后会默认从0开始 for(int i = 0; i<n; ++i) //这里要改为下标0开始 { for(int j = m; j>=goods[i].w; j--) for(int k = K; k>=goods[i].p; k--) { dp[j][k] = max(dp[j][k], dp[j-goods[i].w][k-goods[i].p]+1); } } cout<<dp[m][K]; return 0; }