贪心 + 背包
刷杂技的牛和背包的结合。
按体积和价值的和排序后,按这样顺序选择和一定最大(证明看耍杂技的牛), 然后再通过 01背包在 体积的限制下 选出最大的价值
#include <cstring>
#include <iostream>
#include <algorithm>
#define v first
#define w second
using namespace std;
typedef pair<int, int> PII;
const int N = 2010, M = 40010;
int n, m;
PII cow[N];
int f[M];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> cow[i].v >> cow[i].w, m += cow[i].v;
sort(cow + 1, cow + 1 + n, [&](PII a, PII b) {
return a.v + a.w < b.v + b.w;
});
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= cow[i].v; j -- )
if (j - cow[i].v <= cow[i].w)
f[j] = max(f[j], f[j - cow[i].v] + cow[i].w);
int res = 0;
for (int i = 1; i <= m; i ++ ) res = max(res, f[i]);
cout << res << endl;
return 0;
}
#include <cstring>
#include <iostream>
#include <algorithm>
#define v first
#define w second
using namespace std;
typedef pair<int, int> PII;
const int N = 2010, M = 40010;
int n, m;
PII cow[N];
int f[M];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> cow[i].v >> cow[i].w, m += cow[i].v;
sort(cow + 1, cow + 1 + n, [&](PII a, PII b) {
return a.v + a.w < b.v + b.w;
});
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= cow[i].v; j -- )
if (j - cow[i].v <= cow[i].w)
f[j] = max(f[j], f[j - cow[i].v] + cow[i].w);
else
f[j] = max(f[j], f[j - (j - cow[i].w)] + cow[i].w);
cout << f[m] << endl;
return 0;
}