怕忘了,贴上来吧

递推公式:

f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

Sample Code


 1 #include<stdio.h>
 2 int c[10][100];/*对应每种情况的最大价值*/
 3 int knapsack(int m,int n)
 4 {
 5  int i,j,w[10],p[10];
 6  for(i=1;i<n+1;i++)
 7         scanf("\n%d,%d",&w[i],&p[i]);
 8  for(i=0;i<10;i++)
 9       for(j=0;j<100;j++)
10            c[i][j]=0;/*初始化数组*/
11  for(i=1;i<n+1;i++)
12       for(j=1;j<m+1;j++)
13            {
14             if(w[i]<=j) /*如果当前物品的容量小于背包容量*/
15                      {
16                       if(p[i]+c[i-1][j-w[i]]>c[i-1][j])
17 
18                            /*如果本物品的价值加上背包剩下的空间能放的物品的价值*/
19 
20                          /*大于上一次选择的最佳方案则更新c[i][j]*/
21                             c[i][j]=p[i]+c[i-1][j-w[i]];
22                             else
23                             c[i][j]=c[i-1][j];
24                      }
25               else c[i][j]=c[i-1][j];
26             }
27  return(c[n][m]);
28                     
29 }
30 int main()
31 {
32     int m,n;int i,j;
33     scanf("%d,%d",&m,&n);
34     printf("Input each one:\n");
35     printf("%d",knapsack(m,n));
36     printf("\n");/*下面是测试这个数组,可删除*/
37      for(i=0;i<10;i++)
38       for(j=0;j<15;j++)
39          {
40           printf("%d ",c[i][j]);
41              if(j==14)printf("\n");
42          }
43     system("pause");
44 }
45