首页 > 编程语言 > 详细

算法模板:动态规划(背包问题)

时间:2020-09-21 22:10:28      阅读:55      评论:0      收藏:0      [点我收藏+]
  1. 动态规划:

    • 原理:要满足最优子结构和重叠子问题,使用递归式自底向上计算并保存最优解,找到整体最优解

    • 与贪心的一些区别:

      • 满足贪心一定满足最优子结构,但满足最优子结构不一定满足贪心选择性质,比如背包问题
    • 基本模板

      1. 01背包

        for(i=0; i<n; i++) {
            for(j=m; j>w[i]; j--) { //m -> max weight
                f[j] = max(f[j],f[j-w[i]]+v[i]);
            }
        }
        
      2. 完全背包

        for(i=0; i<n; i++) {
            for(j=w[i]; j<=m; j++) {
                f[j] = max(f[j],f[j-w[i]]+v[i]);
            }
        }
        
      3. 多重背包

        while(n--) {
            ret = s; //rest things
            k = 1; //2>>k
            while(rest >= k) {
                w[++cnt] = w0*k;
                c[cnt] = c0*k;
                rest = rest-k;
                k *= 2;
            }
            if(rest>0) {
                w[++cnt]=w0*rest;
                c[cnt]=c0*rest;
            }
        }
        for(i=1; i<=cnt; i++) {
        	for(j=v; j>=w[i]; j--) {
                dp[j] = max(dp[j],dp[j-w[i]]+c[i]);
            }
        }
        

算法模板:动态规划(背包问题)

原文:https://www.cnblogs.com/syisyuan/p/13708462.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!