动态规划 01背包问题

Danmoits

原题：https://www.luogu.com.cn/problem/P2392

这个代码来自题解，注释是题解自带的（我没有完全理解，尤其是01背包那里），星号括起来的代码看不懂，求大神详细解释下，谢谢！

1. #include <stdio.h>
   
2. int a[5],i,j,k,sum,t,homework[21],dp[2501];
   
3. int max(int a,int b){
   
4.         if(a>=b) return a;
   
5.         else return b;
   
6. }
   
7. int main(){
   
8.         for(i=1;i<=4;i++)
   
9.                 scanf("%d",&a[i]);
   
10.         for(i=1;i<=4;i++){
    
11.                 sum=0;
    
12.                 for(j=1;j<=a[i];j++){
    
13.                         scanf("%d",&homework[j]);
    
14.                         sum+=homework[j];
    
15.                         //算出总时间
    
16.                 }
    
17. *************************************************************
    
18.                 for(j=1;j<=a[i];j++)
    
19.                         for(k=sum/2;k>=homework[j];k--)//只要是总和的一半
    
20.                                 dp[k]=max(dp[k],dp[k-homework[j]]+homework[j]);//01背包
    
21.                 t+=sum-dp[sum/2];//累加为另一个脑子
    
22.                 for(j=1;j<=sum/2;j++)//清零
    
23.                         dp[j]=0;
    
24.         }
    
25. *************************************************************
    
26.         printf("%d",t);
    
27.         return 0;
    
28. }

复制代码

Danmoits

DD