头像

coderlee




离线:2019-11-24 05:43



coderlee
2019-10-24 02:10
#include<iostream>
using namespace std;
const int N=1010;
int f[N][N];
int v[N],w[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=n;i>=1;i--){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i+1][j];
            if(j>=v[i]) f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
        }
    }
    int tmp=m;
    for(int i=1;i<=n;i++){
        if(tmp-v[i]>=0&&f[i][tmp]==f[i+1][tmp-v[i]]+w[i]) {//tmp-v[i]>=0,只有当前物品能放进去,才比较放与不放的价值大小,如果放不进去,直接下一个物品
            cout<<i<<' ';
            tmp-=v[i];
        }
    }
    return 0;
}



coderlee
2019-10-23 14:32
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010, mod=1000000007;
int f[N],g[N];
int main()
{   
    fill(g,g+N,1);//初始化为1
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        int v,w;
        cin>>v>>w;
        for(int j=m;j>=v;j--){
            int tmp,s=0;
            tmp=max(f[j],f[j-v]+w);
            if(tmp==f[j]) s+=g[j];
            if(tmp==f[j-v]+w) s+=g[j-v];
            if(s>=mod) s-=mod;
            f[j]=tmp;
            g[j]=s;
        }
    }
    cout<<g[m]<<endl;返回最终状态的g就是答案
    return 0;
}