[ create a new paste ] login | about

Link: http://codepad.org/jYBXaS1C    [ raw code | output | fork ]

C++, pasted on Sep 23:
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll dp[1001][6002];
ll vis[1001][6002];
ll N,t;
ll w[1001],cap[1001];

ll knapsack(ll i,ll amount,ll k){
    if(i==N+1){
        if(amount>=0)
            return k;
        else return k-1;
    }
    if(amount<0)
        return k-1;
    if(vis[i][amount]==t)
        return dp[i][amount];
    ll p1=0,p2=0;
    p1=knapsack(i+1,min(amount-w[i],cap[i]),k+1);
    p2=knapsack(i+1,amount,k);
    vis[i][amount]=t;
    return dp[i][amount]=max(p1,p2);
}

int main(){
    t=1;
    while(scanf("%lld",&N)==1){
        if(N==0) break;
        ll i;
        for(i=1;i<=N;i++){
            scanf("%lld %lld",&w[i],&cap[i]);
        }

        ll ans=knapsack(1,6001,0);
        printf("%lld\n",ans);
        t++;
    }
}


Output:
1
2
3
Line 23: error: bits/stdc++.h: No such file or directory
Line 4: error: ISO C++ does not support 'long long'
compilation terminated due to -Wfatal-errors.


Create a new paste based on this one


Comments: