01背包-记忆型递归

悠悠 2023-07-18 14:25 22阅读 0赞

有n个重量和价值分别为wi,vi的物品，从这些物品中挑选出总重量不超过W的物品，求最大价值

import java.util.*;
    
    public class ll {
        
        static int[] w={
        2,1,3,2};
        static int[] v={
        3,2,4,2};
        static int n=4;
        static int W=5;
    
        static int dfs(int i,int ww){
        //O(2^n)复杂度
            if (ww<=0) return 0;//装不进去了
            if (i==n) return 0;//0到n-1，没有容量了
            int v2=dfs(i+1,ww);//不选
            if (ww>=w[i]){
        
                int v1=v[i]+dfs(i+1,ww-w[i]);//选
                return Math.max(v1,v2);
            }else {
        
                return v2;
            }
        }
    
        static int m(int i, int ww){
        //优化，记忆型递归，减少了重复计算
            if (ww<=0) return 0;
            if (i==n) return 0;
            if (rec[i][ww]>=0){
        
                return rec[i][ww];
            }
            int ans=0;
            int v2=m(i+1,ww);
            if (ww>=w[i]){
        
                int v1=v[i]+m(i+1,ww-w[i]);
                ans=Math.max(v1,v2);
            }else {
        
                rec[i][W]=ans;//把之前求出来的结果存起来
                return ans;
            }
            rec[i][ww]=ans;//把之前求出来的结果存起来
            return ans;
        }
        static int rec[][];
        public static void main(String[] args) {
        
            int ww=W;
            int ans=dfs(0,ww);
            System.out.println(ans);
            ww=W;
            rec=new int[n][W+1];
            for (int i = 0; i <n ; i++) {
        
                Arrays.fill(rec[i],-1);
            }
    
            ans=m(0,ww);
            System.out.println(ans);
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，22人围观）

还没有评论，来说两句吧...

相关阅读

相关 01背包,从简单递归到递归记忆化搜索到动态规划

[原题链接][Link 1] [左神(左程云)视频讲解][Link 2] 递归版递归考虑思路,从第一块物品开始我们根据当前背包剩余的容量有两种选择第一种是选择当

ゝ一纸荒年。/ 2024年03月26日 17:45/ 0 赞/ 222 阅读

相关 01背包-记忆型递归

有n个重量和价值分别为wi,vi的物品，从这些物品中挑选出总重量不超过W的物品，求最大价值 import java.util.; public

悠悠/ 2023年07月18日 14:25/ 0 赞/ 23 阅读

相关递归实现指数型枚举（递归）

> 写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。这篇博客来详解一下递归实现指数型枚举。如果博客中有不

た入场券/ 2022年11月30日 12:44/ 0 赞/ 267 阅读

相关递归-＞记忆化搜索-＞严格表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

￡神魔★判官ぃ/ 2022年08月31日 16:18/ 0 赞/ 574 阅读

相关 01背包,完全背包

01背包问题：一个背包总容量为V，现在有N个物品，第i个物品体积为weight\[i\]，价值为value\[i\]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？

男娘i/ 2022年06月09日 04:16/ 0 赞/ 379 阅读

相关算法总结01-递归

枚举：子问题横向同类的递归：逐级分解，纵向分解同类的。直接调用，间接调用。递归三要点：递归式，递归出口，界函数。递推公式递归终止条件注意栈的溢

旧城等待，/ 2022年06月03日 01:10/ 0 赞/ 311 阅读

相关 01背包

01背包 > 且说上一周的故事里，小Hi和小Ho费劲心思终于拿到了茫茫多的奖券！而现在，终于到了小Ho领取奖励的时刻了！ > > 小Ho现在手上有M张奖券，而奖品区有N

水深无声/ 2022年05月31日 06:29/ 0 赞/ 915 阅读

相关 C程序-回溯法（递归形式）解决01背包和n后问题

1. 0-1背包问题 n=3的0/1背包问题，设物品质量w=\{18,14,16\}; 物品价值v=\{48,30,30\}; 背包容量c=30. 程序如下所示：

分手后的思念是犯贱/ 2022年05月26日 00:58/ 0 赞/ 294 阅读

相关浅显易懂讲解——动态规划（记忆化递归）

1、动态规划什么时候使用动态规划呢？ Those who cannot remember the past well are condemned to repeat

本是古典何须时尚/ 2022年05月19日 10:08/ 0 赞/ 350 阅读

相关 s01串（递归）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

亦凉/ 2022年05月14日 17:08/ 0 赞/ 313 阅读