简单01背包

怼烎@ 2023-07-15 02:59 11阅读 0赞

package com.company;
    
    import java.util.concurrent.locks.Lock;
    
    public class Main { 
    
        public static void main(String[] args) { 
            /* 每种物品只选一次 */
            //物体的体积和价值
            int[] c = new int[0];
            int[] w = new int[0];
            int v = 0;//背包容量
            int n = 0;//物体总个数
            int[][] f;
            //dp[i][j] 表示只考虑前i件物品，恰好放入一个容量为j的背包可以获得的最大价值
            int dp[][] = new int[0][];
            for (int i = 1; i <= n; i++) { 
                for (int j = 0; j <= v; j++) { 
                    if (j < c[i]) { 
                        dp[i][j] = dp[i - 1][j];
                    } else { 
                        //第i个物品不放与放
                        //dp[i-1][j] 不放，就是上一个物品的价值
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i]);
                    }
                }
            }
        }
    
        void 简单01背包(int[] c, int[] w, int v, int n) { 
            /* 优化，每次只是用了[i-1],完全可以使用一维数组代替,之前的不用存 */
            int[] dp = new int[0];
            for (int i = 1; i <= n; i++) { 
                //确保不会出现一个物品被选多次
                for (int j = v; j >= 0; j--) { 
                    if (j < c[i]) break;
                    dp[j] = Math.max(dp[j], dp[j - c[i]] + w[i]);
                }
            }
            System.out.println(dp[v]);
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 01背包问题的简单理解

对于0/1背包问题,是一类比较经典的问题,主要就是对于物品是否放入背包的一个考量,从难易程度上来说,个人感觉二维的比一维的更好理解. 对于二维,整个dp数组的推倒过程就是从左

灰太狼/ 2024年04月03日 12:50/ 0 赞/ 83 阅读

相关简单01背包

package com.company; import java.util.concurrent.locks.Lock; publi

怼烎@/ 2023年07月15日 02:59/ 0 赞/ 12 阅读

相关 01背包

01背包题目描述给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个输入的第一行包

爱被打了一巴掌/ 2022年12月04日 04:27/ 0 赞/ 204 阅读

相关 01背包,完全背包

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

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

相关 01背包

> 题目：有一个背包，体积为m，现在给你n个石头，每个石头都有价值和体积，问这个背包可以装下多大价值的石头。 > > 输入： > 第一行两个整数n，m，分别代表石头的个数

╰半夏微凉°/ 2022年06月08日 09:37/ 0 赞/ 237 阅读

相关 Bone Collector -简单01背包

Bone Collector Problem Description Many years ago , in Teddy’s hometown there

拼搏现实的明天。/ 2022年06月06日 09:06/ 0 赞/ 165 阅读

相关 01背包

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

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

相关背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这

末蓝、/ 2022年05月30日 10:10/ 0 赞/ 398 阅读

相关背包问题-01背包，完全背包，多重背包

背包问题-01背包，完全背包，多重背包 -------------------- 01背包：概念：有Goods\_Num件物品，MAX\_V

太过爱你忘了你带给我的痛/ 2022年05月14日 09:23/ 0 赞/ 328 阅读

相关 B - Bookshelf 2（01背包简单变形）

题目描述 Farmer John recently bought another bookshelf for the cow library, but the s

约定不等于承诺〃/ 2022年02月24日 06:44/ 0 赞/ 233 阅读