1103: 开心的金明

解题思路:

注意事项:

参考代码:

#include<stdio.h>

int max(int a,int b)

{

    return a>b?a:b;

}

int main()

{

    int N,m;//N表示总钱数,m表示物品件数

    int i,j;

    int ds[1000][30000]={0};

    int v[1000],p[1000];

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

    for(i = 1;i <= m;i++) 

    {

        scanf("%d%d",&v[i],&p[i]);//v物品价格,p物品重要度;

    }

    for(i = 1;i <=m;i++) 

    {

        for(j = 0;j <= N;j++) 

        {

            if(j>=v[i])

            {

                ds[i][j]=max(ds[i-1][j],ds[i-1][j-v[i]]+v[i]*p[i]);

            }

            else

            {

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

            };

        }

    }

    printf("%d",ds[m][N]);

    return 0;

}