【金明的预算方案】 （C语言代码）

解题思路: 01背包问题
注意事项:

利用01背包问题但是二位数组无法达到32000

参考代码:

#include<stdio.h>

int main()

{

        int x,y,z,d,a[61][3200]={0},b[61],n[61],m[61],j,k,l,p[61][3200];

        scanf("%d%d",&x,&y);

        x=x/10;//（因为二位数组无法到达32000而且题目已经说了钱数都是10的倍数）

        for(z=1;z<=y;z++)

        scanf("%d%d%d",&b[z],&n[z],&m[z]);

        for(z=1;z<=y;z++)

        b[z]=b[z]/10;//（将物品的价格也降低10倍）

        for(z=1;z<=y;z++)

        {

            for(j=1;j<=x;j++)

            {

                if(j<b[z])

                a[z][j]=a[z-1][j];

                else

                {

                    if(m[z]==0)

                    {

                        if(a[z-1][j]>a[z-1][j-b[z]]+b[z]*10*n[z])

                        a[z][j]=a[z-1][j];

                         else

                        a[z][j]=a[z-1][j-b[z]]+b[z]*10*n[z];

                        p[z][j]=z;

                    }

                        else

                        {

                            for(l=0;l<=z;l++)

                            {

                                if(p[z][j]==m[z])

                                {

                                    if(a[z-1][j]>a[z-1][j-b[z]]+b[z]*10*n[z])

                                    a[z][j]=a[z-1][j];

                                    else

                                    a[z][j]=a[z-1][j-b[z]]+b[z]*10*n[z];

                                }

                                else

                                a[z][j]=a[z-1][j];

                            }

                        }

                    }

                }

            }

        printf("%d\n",a[y][x]);

        return 0;

}