学步园

题意:

给出n个物品,背包容量为v;

每个物品体积ti为1或者2, 价值为pi

求背包中所能装物品的最大价值.

思路:

贪心:经过分析可以发现,拿物品的优先顺序是不会交换的----如果要拿此种物品,必然拿剩下的此种物品中单位价格最高的.同时考虑拿两种物品时,差异只在于拿物品的数量.

因此可以分别存储,降序排序后计算前i项和(i = 1 .. n),然后枚举进行匹配,最大的一组即是答案.

细节:注意各个数组,循环中下标分别是从1还是0开始的!容易混乱呐~!

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

typedef struct vehicle
{
    int id,capa;
}vehi;
bool cmp(vehi a,vehi b)
{
    return a.capa>b.capa;
}
vehi v1[100005],v2[100005];
int sum1[100005],sum2[100005];

int main()
{
    int n,v;
    cin>>n>>v;
    int p1 = 0,p2 = 0;
    for(int i=0;i<n;i++)
    {
        int t,c;
        cin>>t>>c;
        if(t&1)
        {
            v1[p1].capa = c;
            v1[p1++].id = i;
        }
        else
        {
            v2[p2].capa = c;
            v2[p2++].id = i;
        }
    }
    sort(v1,v1+p1,cmp);
    sort(v2,v2+p2,cmp);
    sum1[0] = sum2[0] = 0;
    for(int i=1;i<=p1;i++)
        sum1[i] = sum1[i-1] + v1[i-1].capa;
    for(int i=1;i<=p2;i++)
        sum2[i] = sum2[i-1] + v2[i-1].capa;
    int pic1,pic2,rest,hi1 = 0,hi2 = 0,ans = 0;
    for(pic1 = 0;pic1<=p1;pic1++)
    {
        if(pic1>v) break;
        rest = v - pic1;
        if(rest>=p2*2)  pic2 = p2;
        else    pic2 = rest>>1;
        int tc = sum1[pic1]+sum2[pic2];
        if(ans<tc)
        {
            ans = tc;
            hi1 = pic1;
            hi2 = pic2;
        }
    }
    cout<<ans<<endl;
    if(hi2>0)
    {
        for(int i=0;i<hi1;i++)
            printf("%d ",v1[i].id+1);
        for(int i=0;i<hi2;i++)
            printf("%d%c",v2[i].id+1,(i==hi2-1)?'\n':' ');
    }
    else
    {
        for(int i=0;i<hi1;i++)
            printf("%d%c",v1[i].id+1,(i==hi1-1)?'\n':' ');
    }

}