开心的金明-背包问题解法

解题思路:可归纳为背包问题

注意事项:放入二维数组的是单件物品*权重

参考代码:

#include<stdio.h>

int max(int a,int b)

{

    int max=0;

    max = a>b?a:b;

    return max;

}

int main()

{

    int sum_all,num_all,C[50],V[50],maxCV[100][40000]={0};

    scanf("%d%d",&sum_all,&num_all);

    for(int i=1;i<=num_all;i++)

    {

        scanf("%d%d",&C[i],&V[i]);

    }

    for(int j=1;j<=num_all;j++)

    {

        for(int k=1;k<=sum_all;k++)

        {

            if(k>=C[j])

            {

                maxCV[j][k] = max(maxCV[j-1][k-C[j]] +V[j]*C[j],maxCV[j-1][k]);

            }

            else

            {

                maxCV[j][k] = maxCV[j-1][k];

            }

        }

    }

    printf("%d",maxCV[num_all][sum_all]);

    return 0;

}