怕忘了，貼上來吧

遞推公式：

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