首页 > 代码库 > 动态规划 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 }
参考数据:
10,3
3,4
4,5
5,6
动态规划 01背包
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。