学习总结2.14

深搜将题目分配，如果是两个题目，就可以出现左左，左右，右左，右右四种时间分配，再在其中找最小值，即是两脑共同处理的最小值

#include <stdio.h> int s[4]; int sum=0; int brain[25][25]; int min=999; int left=0,right=0; void dfs(int x,int y){ if(y>s[x]){//如果当前这套题目已经被复习完 if(max(left,right)<min) min=max(left,right);//更新最小值 return; }else{ left+=brain[x][y];//左脑处理 dfs(x,y+1);//递归 left-=brain[x][y];//回溯 right+=brain[x][y];//右脑处理 dfs(x,y+1);//递归 right-=brain[x][y];//回溯 } } int max(int a,int b){ return (a>b)?a:b; } int main() { for(int i=1;i<=4;i++){ scanf("%d",&s[i]); } for(int i=1;i<=4;i++){ left=0,right=0; min=999;//初始化 for(int j=1;j<=s[i];j++){ scanf("%d",&brain[i][j]); } dfs(i,1); sum+=min; } printf("%d\n",sum); return 0; }

比较简单的dp01背包

#include <stdio.h> int dp[205][205]={0}; int n,m,t; int a[205],b[205]; int max(int a,int b){ return (a>b)?a:b; } int main() { scanf("%d %d %d",&n,&m,&t); for(int i=1;i<=n;i++){ scanf("%d %d",&a[i],&b[i]); } for(int i=1;i<=n;i++){ for(int j=m;j>=a[i];j--){ for(int k=t;k>=b[i];k--){ dp[j][k]=max(dp[j][k],dp[j-a[i]][k-b[i]]+1); } } } printf("%d\n",dp[m][t]); return 0; }