1924: 蓝桥杯算法提高VIP-01背包

解题思路:

注意事项: dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);    dp[i][j]表示有i个物品传入，背包能装j的重量
参考代码:

#include<stdio.h>

#include<stdlib.h>

# define N 201

# define M 5001

int max(int a,int b){

    return a>b?a:b;

}

int main()

{

    int n,m;

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

    int w[201],v[201];

    int dp[N][M]={0};

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

        scanf("%d%d",&w[i],&v[i]);

    }

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

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

            if(j<w[i]){

                dp[i][j]=dp[i-1][j];

            }else{

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

            }

        }

    }

    int max_dp=0;

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

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

             max_dp=max(max_dp,dp[i][j]);

        }

    }

    printf("%d",max_dp);

return 0;

}