动态规划 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("
%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                       else
19                               c[i][j]=c[i-1][j];
20              }
21              else
22                      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:
");
32     scanf("%d,%d",&m,&n);
33     printf("Input each one(weight and value):
");
34     printf("%d",knapsack(m,n));
35     printf("
");
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("
");
42         }
43     return 0;
44 }

View Code

参考数据：

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

左边是重量，

右边是价值。

我把输出改了改，理解上会容易些：

 1 #include<stdio.h>
 2 int cum_vol,num;
 3 int volu[100],val[100];
 4 int dp[100][100];
 5 int main()
 6 {
 7     freopen("a.txt","r",stdin);
 8     int i,j,k;
 9     while(scanf("%d,%d",&cum_vol,&num)==2)
10     {
11         for(i=1;i<=num;i++)
12         {
13             scanf("%d,%d",&volu[i],&val[i]);
14         }
15         for(i=0;i<=num;i++)
16             for(j=0;j<=cum_vol;j++)
17                 dp[i][j]=0;
18 
19         for(i=1;i<=num;i++)
20             for(j=1;j<=cum_vol;j++)
21             {
22                 if(volu[i]<=j)
23                 {
24                     if(val[i]+dp[i-1][j-volu[i]]>dp[i-1][j])
25                         dp[i][j]=val[i]+dp[i-1][j-volu[i]];
26                     else
27                         dp[i][j]=dp[i-1][j];
28                 }
29                 else
30                     dp[i][j]=dp[i-1][j];
31             }
32             
33         for(i=0;i<=num;i++)
34         {
35             printf("
");
36             for(j=0;j<=cum_vol;j++)
37                 printf("%-4d",dp[i][j]);
38         }
39     }
40     return 0;
41 }

View Code