开心的金明 （C语言代码）

递归：

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

int n,m;
typedef struct Node
{
    int price;
    int value;
}node;
node *a;
/**递归：在第1，2，...，k号物品的“价格与重要度之积总和”已经达最大值的条件下（总价格不超过n），
当且仅当第k+1，k+2，...，m号物品的“价格与重要度之积总和”达最大值（总价格不超过n），
才有第1，2，...，m号的“价格与重要度之积总和”达最大值（总价格不超过n）
**/
int calc(int i,int capacity)
{
    if(i==m) return (capacity<a[i].price)?0:(a[i].price*a[i].value);
    if(capacity<a[i].price) return calc(i+1,capacity);
    return max(calc(i+1,capacity),calc(i+1,capacity-a[i].price)+(a[i].price*a[i].value));
}

int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
    int i,res;
    scanf("%d %d",&n,&m);
    getchar();

    a=(node*)malloc(sizeof(node)*(m+1));
    for(i=1;i<=m;i++)
        scanf("%d %d",&a[i].price,&a[i].value);
    res=calc(1,n);
    printf("%d",res);

    free(a);
    return 0;
}

递归（无重复计算）

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

int n,m;
typedef struct Node
{
    int price;
    int value;
}node;
node *a;

int **store;

int calc(int i,int capacity)
{
    if(store[i][capacity]>=0) return store[i][capacity];
    if(i==m)
        {
            store[i][capacity]=(capacity<a[i].price)?0:(a[i].price*a[i].value);
            return store[i][capacity];
        }
    if(capacity<a[i].price) store[i][capacity]=calc(i+1,capacity);
    else store[i][capacity]=max(calc(i+1,capacity),calc(i+1,capacity-a[i].price)+(a[i].price*a[i].value));

    return store[i][capacity];
}

int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
    int i,j,res;
    scanf("%d %d",&n,&m);
    getchar();
    //以下是初始化store数组
    store=(int**)malloc(sizeof(int*)*(m+1));
    for(i=0;i<=m;i++)
        store[i]=(int*)malloc(sizeof(int)*(n+1));
    for(i=0;i<=m;i++)
        for(j=0;j<=n;j++)
            store[i][j]=-1;
    //以下是初始化a数组，存储price和对应value
    a=(node*)malloc(sizeof(node)*(m+1));
    for(i=1;i<=m;i++)
        scanf("%d %d",&a[i].price,&a[i].value);
    //以下是计算结果并输出
    res=calc(1,n);
    printf("%d",res);
    
    //
    for(i=0;i<=m;i++) free(store[i]);
    free(store);
    free(a);
    return 0;
}