J.溪染的优惠券(贪心01背包)

LINK

有点像背包,但是又不完全是

原因在于使用的物品有限制,使得物品的使用次序是未知的

这样显然无法扫一遍做背包

如果按照排序也是不对的,限制大的不一定先使用

若使用变为,这样中间错过了许多小型优惠劵,可能先使用中间的才更优

于是想到按照排序,直接做背包即可.

这样选择物品的顺序满足

如果只选择优惠券中的一个,那么顺序是无所谓的,背包会考虑到

如果需要同时选择物品,那么按照的顺序一定是可行的

反证法

设按照的顺序选可行得到

按照顺序选优惠券不可行得到

我们得到,也就是

而因为,移项得到

显然矛盾,证毕,不存在这种情况.

也就是说,按照这种方式排序不会错,直接做背包即可

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
int n,k,vis[maxn],s[maxn],f[maxn];
typedef pair<int,int>p;
p a[maxn];
bool com(p a,p b)
{
    if( a.first-a.second==b.first-b.second )    return a.first<b.first;
    return a.first-a.second>b.first-b.second;
}
int main()
{
    cin >> n >> k;
    for(int i=1;i<=n;i++)    cin >> a[i].first >> a[i].second;
    f[k] = 1;
    sort( a+1,a+1+n,com );
    for(int i=1;i<=n;i++)
    for(int j=a[i].first;j<=k;j++)
        f[j-a[i].second] |= f[j];
    int ans = k;
    for(int i=0;i<=k;i++)
        if( f[i] ){    cout << i; return 0; }
}