【金明的预算方案】 （C语言代码）——动态规划

解题思路:参考题号1103“开心的金明”

参考代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct{
    int v;
    int p;
    int q;
}item;
item *a;
int *picked;
int N,m;

int pick(int rem, int i)
{

   if(a[i].q==0||picked[a[i].q-1]==1){
        if(i==m-1)
            {
                if(rem<a[i].v) return 0;
                else return (a[i].v*a[i].p);
            }
        int res1=0,res2=0;
        if(rem<a[i].v) return pick(rem,i+1);

        res1=pick(rem,i+1);
        picked[i]=1;
        res2=pick(rem-a[i].v,i+1)+a[i].v*a[i].p;
        picked[i]=0;
        return res1>res2?res1:res2;
   }
   else if(i==m-1&&a[i].q==1&&picked[a[i].q-1]==0) return 0;
   return pick(rem,i+1);
}


int main()
{
    int i;
    scanf("%d %d",&N,&m);
    getchar();
    a=(item *)malloc(sizeof(item)*m);
    picked=(int *)malloc(sizeof(int)*(m+1));
    for(i=0;i<=m;i++) picked[i]=0;
    for(i=0;i<m;i++) scanf("%d %d %d",&a[i].v,&a[i].p,&a[i].q);
    printf("%d",pick(N,0));
    free(a);free(picked);
    return 0;
}