lintcode 700. 杆子分割完全背包

超、凢脫俗 2023-07-25 12:35 31阅读 0赞

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

样例
    样例1
    
    输入：
    [1, 5, 8, 9, 10, 17, 17, 20]
    8
    输出：22
    解释：
    长度    | 1   2   3   4   5   6   7   8  
    --------------------------------------------
    价格    | 1   5   8   9  10  17  17  20
    切成长度为 2 和 6 的两段。
    样例2
    
    输入：
    [3, 5, 8, 9, 10, 17, 17, 20]
    8
    输出：24
    解释：
    长度    | 1   2   3   4   5   6   7   8  
    --------------------------------------------
    价格    | 3   5   8   9  10  17  17  20
    切成长度为 1 的 8 段。

思路：计算每一种方案把杆子切割完后的最大值即可

class Solution {
        
    public:
        /**
         * @param prices: the prices
         * @param n: the length of rod
         * @return: the max value
         */
        int cutting(vector<int> &prices, int n) {
        
            // Write your code here
            vector<int> dp(n+1,0);
            for (int i = 1; i <= prices.size(); i++) {
        
                for(int j = i; j <=n;j++)
                {
        
                    dp[j]=max(dp[j],dp[j-i]+prices[i-1]);
                }
            }
            return dp[n];
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 nyoj 311 完全背包（dp--完全背包）

完全背包时间限制： 3000 ms | 内存限制： 65535 KB 难度： 4 描述直接说题意，完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件

系统管理员/ 2024年02月17日 20:51/ 0 赞/ 41 阅读

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

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

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

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

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

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

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

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

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

相关完全背包

完全背包在背包九讲中有很详细的讲解，但是今天碰到题尝试了一下他给的算法，发现并不快，看了一下其他的代码，速度很快！题目链接http://hihocoder.com/prob

拼搏现实的明天。/ 2022年08月21日 02:16/ 0 赞/ 233 阅读

相关 01背包,完全背包

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

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

相关完全背包

完全背包和01背包的区别 > 01背包：有n个物品，每种物品只能被使用一次 > > 完全背包：有n个物品，每个物品可以被多次使用完全背包的递推公式可以由01背包的递推公

ゞ浴缸里的玫瑰/ 2022年06月08日 09:43/ 0 赞/ 232 阅读

相关完全背包

问题：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量

今天药忘吃喽~/ 2022年05月31日 01:05/ 0 赞/ 241 阅读

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

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

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

相关 0-1背包&完全背包

First：0-1背包问题 1.定义define：所谓的0-1背包就是指每种物品只有一件，而每件物品只有两种选择，即选择放或是不放 2.问题：一个小偷来出来活动

桃扇骨/ 2022年05月28日 12:24/ 0 赞/ 236 阅读