knapsack2.cpp

这是经典的背包问题

#include<iostream>
#include<stdio.h>
using namespace std;
#define MAXN 1000 +10
#define MAXC 10000 +10
int w[MAXN],p[MAXN];
int f[MAXC];
int n,c,ans;
void solve()
{
    int i,j;
    memset(f,0,sizeof(f));
    for(i=1;i<=n;i++)
    {
        for(j=c;j>=0;j--)
        if(j+w[i]<=c)
        {
            if(f[j]+p[i]>f[j+w[i]])
            {
                f[j+w[i]]=f[j]+p[i];
                if(f[j]+p[i]>ans) ans=f[j]+p[i];
            }
        }
    }
}
int main()
{
    int i;
    freopen("input4.txt","r",stdin);
    scanf("%d%d",&n,&c);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&w[i],&p[i]);
    }
    ans=0;
    solve();
    printf("%d\n",ans);
    system("pause");
    while(1);
    return 0;
}