首页 > 代码库 > 动态规划 01背包

动态规划 01背包

技术分享
 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                               c[i][j]=p[i]+c[i-1][j-w[i]];18                       else19                               c[i][j]=c[i-1][j];20              }21              else22                      c[i][j]=c[i-1][j];23      }24      return(c[n][m]);25 }26 int main()27 {28     freopen("a.txt","r",stdin);29     int m,n;int i,j;30 31     printf("input the max capacity and the number of the goods:\n");32     scanf("%d,%d",&m,&n);33     printf("Input each one(weight and value):\n");34     printf("%d",knapsack(m,n));35     printf("\n");36     for(i=0;i<10;i++)37         for(j=0;j<15;j++)38         {39              printf("%-4d",c[i][j]);40              if(j==14)41                  printf("\n");42         }43     return 0;44 }
View Code

参考数据:

10,3
3,4
4,5
5,6 

动态规划 01背包