knapsack3.cpp

这是经典的背包问题

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
struct item
{
    int w,p;
};
vector<item> s;
int n,c;
int ans,cur;
void solve()
{
    int i,m=c;
    for(i=0;i<n;i++)
    if(s[i].w<=m)
    {
        m-=s[i].w;
        ans+=s[i].p;
    }
    for(i=0;i<n;i++)
    if(s[i].w<=c&&s[i].p>ans)
    {
        ans=s[i].p;
    }
}
bool cmp(item a,item b)
{
    return double(a.p)/a.w>double(a.p)/a.w;
}

int main()
{
    int i,j,k;
    item tmp;

    freopen("input5.txt","r",stdin);
    cin>>n>>c;
    for(i=1;i<=n;i++)
    {
        cin>>j>>k;
        tmp.w=j;
        tmp.p=k;
        s.push_back(tmp);
    }
    sort(s.begin(),s.end(),cmp);
    ans=0;
    solve();
    printf("%d\n",ans);
    system("pause");
    while(1);
    return 0;
}