lintcode 125. 背包问题 II

比眉伴天荒 2023-07-07 12:38 72阅读 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 条评论，72人围观）

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

相关阅读

相关 lintcode740. 零钱兑换 2 完全背包

给出不同面值的硬币以及总金额. 试写一函数来计算构成该总额的组合数量. 你可以假设每一种硬币你都有无限个. 样例样例1 输入: amoun

痛定思痛。/ 2023年07月25日 12:49/ 0 赞/ 20 阅读

相关 lintcode 700. 杆子分割完全背包

给一个 n 英寸长的杆子和一个包含所有小于 n 的尺寸的价格. 确定通过切割杆并销售碎片可获得的最大值. 样例样例1 输入： [1

超、凢脫俗/ 2023年07月25日 12:35/ 0 赞/ 19 阅读

相关 lintcode 669. 换硬币完全背包

给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1. 样例

约定不等于承诺〃/ 2023年07月25日 11:26/ 0 赞/ 22 阅读

相关 lintcode 125. 背包问题 II

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

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

相关 lintcode198. 排列序号II

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

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

相关 lintcode563. 背包问题 V

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

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

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

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

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

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

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

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

相关 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 赞/ 209 阅读

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

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

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