首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    动态规划之背包问题(C语言)

    动态规划(英语:Dynamic programming,简称DP)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题 动态规划思想大致上为:若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。 由于通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

    01

    OJ算法题

    #include <stdio.h> #include <string.h> #define MAX 1000 struct Node{     int v,net; }; struct Node node[MAX]; int main(){     int n,e,t,i,x,y,z,head[MAX],que[MAX],map[MAX/2][MAX/2],qh,qt;     while(scanf("%d %d",&n,&e)!=EOF){         memset(head,-1,sizeof(head));         for(i = 0;i < e;i++){             scanf("%d %d",&x,&y);             node[i].v = y;             node[i].net = head[x];             head[x] = i;         }         scanf("%d",&t);         while(t--){             z = 0;             memset(map,0,sizeof(map));             qh = qt = 1;             scanf("%d %d",&x,&y);             if(x == y){                 printf("yes\n");                 continue;             }             que[qt++] = x;             while(qh < qt){                 for(i = head[que[qh]];i != -1;i = node[i].net){                     if(map[que[qh]][node[i].v] == 0){                         map[que[qh]][node[i].v] = 1;                         que[qt++] = node[i].v;                     }                     if(node[i].v == y){                         z = 1;                         break;                     }                 }                 if(z == 1) break;                 qh++;             }             if(z == 1) printf("yes\n");             else printf("no\n");         }         printf("\n");     }     return 0; }

    03

    扫码

    添加站长 进交流群

    领取专属 10元无门槛券

    手把手带您无忧上云

    扫码加入开发者社群

    相关资讯

    热门标签

    活动推荐

      运营活动

      活动名称
      广告关闭
      领券