开心的金明<0-1背包>

题意：0-1背包经典题；

不多述，直接上代码：

1.二维数组表示法：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

int dp[30][30005];

int main ()

{

    int R,N;int v,m;

    scanf("%d%d",&R,&N);

    for(int i=1;i<=N;i++){

        scanf("%d%d",&v,&m);

        for(int j=1;j<=R;j++){

            dp[i][j]=(i==1?0:dp[i-1][j]);

            if(j>=v)

                dp[i][j]=max(dp[i][j],dp[i-1][j-v]+v*m);

        }

    }

    printf("%d\n",dp[N][R]);

    return 0;

}

2：一维数组表示法：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

int dp[30005];

int main ()

{

    int R,N;int v,m;

    scanf("%d%d",&R,&N);

    for(int i=1;i<=N;i++){

        scanf("%d%d",&v,&m);

        for(int j=R;j>=v;j--)

                dp[j]=max(dp[j],dp[j-v]+v*m);

    }

    printf("%d\n",dp[R]);

    return 0;

}

巴特西

开心的金明<0-1背包>

最新文章

热门文章