开心的金明-C语言

解题思路: 

    典型0/1背包问题，套用0/1背包问题公式sum[i][j]=max(sum[i-1][j],sum[i-1][j-v[i]]+p[i]*v[i])即可。总钱数N代表背包容量，物品个数m，最大价值总和为sum[i][j]表示前i个物品用不超过j的价格所能达到的最大价值，费用v[25]，重要度p[25]。

注意事项: 

    最大价值总和sum的第0行与第0列均为0，所以费用v与重要度p的输入最好从1开始存，计算也从1开始；sum的类型long long int。

参考代码: 

#include <stdio.h>
#include <stdlib.h>

long long int sum[27][30002]={0};//最大价值
long int v[25]={0};
int p[25]={0};//v为价格，p为重要度
int max(int i,int j)//自定义max函数，返回更大的值
{
    return i>j?i:j;
}
int main()
{
    long int N=0;  //总钱数
    int m=0;       //物品个数
    scanf("%ld %d",&N,&m);
    for(int i=1;i<=m;i++){  //从1开始输入
        scanf("%ld %d",&v[i],&p[i]);
    }
    for(int i=1;i<=m;i++){  //从第1个物品开始判断，需要多少钱才能装进背包中
        for(long int j=1;j=v[i])
                sum[i][j]=max(sum[i-1][j],sum[i-1][j-v[i]]+p[i]*v[i]); //钱到位了，判断值不值当放
            else
                sum[i][j]=sum[i-1][j]; //钱没到位，维持原状
        }
    }
    printf("%lld\n",sum[m][N]);
    return 0;
}