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

解题思路:

注意事项:

参考代码:

/********************0_1背包核心算法*****************************

for (int m=1;m<=M;m++)          //控制并保证每组物品经过0_1

{

for (int n=1;n<=N;n++)

{                                                  //n依次递增，vaule[m]<=n,不成立，即不买（0）；成立，即买（1）

if(vaule[m]<=n)                          //使符合条件的最大值，向矩阵右下端聚集

sum_vaule[m][n]=max(sum_vaule[m-1][n-vaule[m]]+imprtant[m]*vaule[m],sum_vaule[m-1][n]);

else

sum_vaule[m][n]=sum_vaule[m-1][n];

}

算法核心；                       n依次递增，vaule[m]<=n,不成立，即不买（0）；成立，即买（1）

                                       max使符合条件的最大值，向矩阵右下端聚集,

 细节；                  max(sum_vaule[m-1][n-vaule[m]]+imprtant[m]*vaule[m],sum_vaule[m-1][n])

                             保证了选取的每组物品总价值不超过给定价值，

                             可结合参数较小(价值小于20)时的背包图(如下)进行参考；

20 5

3 2

4 3

8 4

9 1

12 3

*********************背包图详解****************************

       6   6   6   6   6   6   6   6   6   6   6   6  6   6    6   6   6   6

       6 12 12 12 18 18 18 18 18 18 18 18 18 18 18 18 18 18

       6 12 12 12 18 32 32 32 38 44 44 44 50 50 50 50 50 50

       6 12 12 12 18 32 32 32 38 44 44 44 50 50 50 50 50 50

       6 12 12 12 18 32 32 32 38 44 44 44 50 50 50 50 54 68

68

*/参见代码

#include<stdio.h>

int sum_vaule[102][100000];

void finish(int *,int*,int ,int);  //0_1背包，选择最大值

void get(void);                    //获取价格及重要度

#define  max(x,y) (x)>(y)?(x):(y)  //找最大

/*************************************************/

int main ()

{

get();                         

return 0;

}

/*************************************************/

void get(void)

{

int N,M;

int vaule[102],imprtant[102];

    while(scanf("%d %d",&N,&M)!=EOF)  //循环获取每组参数，ctrl+d结束

    {

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

{

scanf("%d %d",&vaule[i],&imprtant[i]);

}

finish(vaule,imprtant,N,M);           //参数获取结束，找出最优解

}

return ;

}

/********************0_1背包核心算法*****************************

void finish(int *vaule,int *imprtant,int N ,int M)

{

for (int m=1;m<=M;m++)          //控制并保证每组物品经过0_1

{

for (int n=1;n<=N;n++)

{                                                  //n依次递增，vaule[m]<=n,不成立，即不买（0）；成立，即买（1）

if(vaule[m]<=n)                          //使符合条件的最大值，向矩阵右下端聚集

sum_vaule[m][n]=max(sum_vaule[m-1][n-vaule[m]]+imprtant[m]*vaule[m],sum_vaule[m-1][n]);

else

sum_vaule[m][n]=sum_vaule[m-1][n];

}

}

   /* printf("*********************背包图详解****************************\n");

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

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

    {

     printf("%2.d ",sum_vaule[i][j]);

     if(j%N==0)

     printf("\n");

    }*/

printf("%d\n",sum_vaule[M][N]);//查询结束，打印最大值

}