怕忘了,贴上来吧
递推公式:
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