金矿问题的两解

2008-10-31 20:25

#include<iostream>
using namespace std;
int main(void){
    int people,gold[20],p_n[20],n;
    int f[10010];
    int i,j;
   
    cin>>people>>n;
    for(i=1;i<=n;i++) cin>>p_n[i]>>gold[i];
   
    memset(f,0,sizeof(f));
    for(i=1;i<=n;i++)
        for(j=people - p_n[i];j>=0;j--)
            if(f[j+p_n[i]]<f[j]+gold[i]) f[j+p_n[i]] = f[j]+gold[i];
   
    cout<<f[people];
   
    system("pause");
    return 0;
}
 
#include<iostream>
using namespace std;
int main(void){
    int people,gold[20],p_n[20],n;
    int f[10010][20];
    int i,j,t1,t2;
   
    cin>>people>>n;
    for(i=1;i<=n;i++) cin>>p_n[i]>>gold[i];
   
    memset(f,0,sizeof(f));
    for(i=1;i<=n;i++)
        for(j=people;j>=p_n[i];j--){
            t1 = f[j-p_n[i]][i-1] + gold[i];
            t2 = f[j][i-1];
            f[j][i] = t1>t2?t1:t2;
        }
   
    cout<<f[people][n];
   
    system("pause");
    return 0;
}