lintcode 125. 背包问题 II

比眉伴天荒 2023-07-07 12:38 52阅读 0赞

有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.问最多能装入背包的总价值是多大?

样例
    样例 1:
    
    输入: m = 10, A = [2, 3, 5, 7], V = [1, 5, 2, 4]
    输出: 9
    解释: 装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9 
    样例 2:
    
    输入: m = 10, A = [2, 3, 8], V = [2, 5, 8]
    输出: 10
    解释: 装入 A[0] 和 A[2] 可以得到最大价值, V[0] + V[2] = 10
    挑战
    O(nm) 空间复杂度可以通过, 不过你可以尝试 O(m) 空间复杂度吗?
    
    注意事项
    A[i], V[i], n, m 均为整数
    你不能将物品进行切分
    你所挑选的要装入背包的物品的总大小不能超过 m
    每个物品只能取一次

class Solution {
        
    public:
        /**
         * @param m: An integer m denotes the size of a backpack
         * @param A: Given n items with size A[i]
         * @param V: Given n items with value V[i]
         * @return: The maximum value
         */
        int backPackII(int m, vector<int> &A, vector<int> &V) {
        
            // write your code here
            int len=A.size();
            vector<int> dp(m+1,0);
            for (int i = 0; i < len; i++) {
        
                /* code */
                for(int j = m; j >= 1; j--)
                {
        
                    if(j>=A[i])
                    {
        
                        dp[j]=max(dp[j],dp[j-A[i]]+V[i]);
                    }
                }
            }
            return dp[m];
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 lintcode 125. 背包问题 II

有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.问最多能装入背包的总价值是多大? 样例样例 1:

比眉伴天荒/ 2023年07月07日 12:38/ 0 赞/ 53 阅读

相关 lintcode198. 排列序号II

给出一个可能包含重复数字的排列，求这些数字的所有排列按字典序排序后该排列在其中的编号。编号从1开始。样例样例 1: 输入:[1,4,2,

旧城等待，/ 2023年07月07日 05:56/ 0 赞/ 8 阅读

相关 lintcode563. 背包问题 V

给出 n 个物品, 以及一个数组, nums\[i\] 代表第i个物品的大小, 保证大小均为正数, 正整数 target 表示背包的大小, 找到能填满背包的方案数。每一个

青旅半醒/ 2023年05月22日 04:59/ 0 赞/ 9 阅读

相关 5 多重背包问题 II（二进制优化-转为零一背包问题求解）

1. 问题描述：有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。求解将哪些物品装入背包，可使物品体积总和不超过背包容

一时失言乱红尘/ 2022年09月11日 06:16/ 0 赞/ 152 阅读

相关 518 零钱兑换 II（完全背包问题）

1. 问题描述：给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑

系统管理员/ 2022年08月30日 04:12/ 0 赞/ 264 阅读

相关 lintcode Coins in Line II 硬币排成线 II

硬币排成线 II [ 描述][Link 1] [ 笔记][Link 2] [ 数据][Link 3] [ 评测][Link 4] 有 `n`

女爷i/ 2022年07月15日 00:44/ 0 赞/ 146 阅读

相关【LintCode 简单】6. 合并排序数组 II

1.问题描述：合并两个排序的整数数组A和B变成一个新的数组。 2.样例：给出A=\[1,2,3,4\]，B=\[2,4,5,6\]，返回 \[1,2,2,3,4

客官°小女子只卖身不卖艺/ 2022年06月01日 05:55/ 0 赞/ 180 阅读

相关 LintCode -- 合并排序数组 II

描述合并两个排序的整数数组A和B变成一个新的数组。样例给出A=\[1,2,3,4\]，B=\[2,4,5,6\]，返回 \[1,2,2,3,4,4,5,6\

朴灿烈づ我的快乐病毒、/ 2022年05月25日 11:12/ 0 赞/ 192 阅读

相关 lintCode-92.背包问题.dp解法

上周软考成绩出来了，当看到成绩的时候感觉还是有点小小的遗憾——差了5分。好几个周末都泡在图书馆里潜心修炼，尽管结果没能达到我的预期，但也让我发现了周末的新玩法-->泡图书馆，在

忘是亡心i/ 2022年05月19日 07:16/ 0 赞/ 210 阅读

相关 Lintcode: Sort Colors II 解题报告

[Sort Colors II ][Sort Colors II] 原题链接： [http://lintcode.com/zh-cn/problem/sort-color

柔光的暖阳◎/ 2022年04月22日 15:26/ 0 赞/ 194 阅读