knapsack1.cpp

这是经典的背包问题

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
struct item
{
    int w,p;
};
vector<item> s;
vector<int> sum;
int n,m;
int ans,cur;
void solve(int x)
{
    if(x==n)
    {
        if(cur>ans) ans=cur;
        return;
    }
    if(cur+sum[x]<=ans) return;
    if(s[x].w<=m)
    {
        m-=s[x].w;
        cur+=s[x].p;
        solve(x+1);
        cur-=s[x].p;
        m+=s[x].w;
    }
    solve(x+1);
}
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("input4.txt","r",stdin);
    cin>>n>>m;
    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);
    for(i=0;i<n;i++)
    {
        k=0;
        for(j=i;j<n;j++)
        {
            k+=s[j].p;
        }
        sum.push_back(k);
    }
    ans=cur=0;
    solve(0);
    printf("%d\n",ans);
    system("pause");
    while(1);
    return 0;
}