lintcode 562. 背包问题 IV完全背包

叁歲伎倆 2023-07-25 11:26 27阅读 0赞

给出 n 个物品, 以及一个数组, nums\[i\]代表第i个物品的大小, 保证大小均为正数并且没有重复, 正整数 target 表示背包的大小, 找到能填满背包的方案数。  
每一个物品可以使用无数次

样例
    样例1
    
    输入: nums = [2,3,6,7] 和 target = 7
    输出: 2
    解释:
    方案有: 
    [7]
    [2, 2, 3]
    样例2
    
    输入: nums = [2,3,4,5] 和 target = 7
    输出: 3
    解释:
    方案有: 
    [2, 5]
    [3, 4]
    [2, 2, 3]

思路：物品重量的数组从小到大有序，一次记录到达每一个重量的方案数和最后到达target的方案数即可

class Solution {
        
    public:
        /**
         * @param nums: an integer array and all positive numbers, no duplicates
         * @param target: An integer
         * @return: An integer
         */
        int backPackIV(vector<int> &nums, int target) {
        
            // write your code here
            int len=nums.size();
            vector<int> dp(target+1,0);
            dp[0]=1;
            for (int i = 0; i < len; i++) {
        
                for(int j = nums[i]; j <= target; j++)
                {
        
                    dp[j]+=dp[j-nums[i]];
                }
            }
            return dp[target];
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

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

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

相关 lintcode 562. 背包问题 IV完全背包

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

叁歲伎倆/ 2023年07月25日 11:26/ 0 赞/ 28 阅读

相关背包DP | 完全背包问题

> 完全背包问题：有n种物品，每一件的物品重量为 w\[ i \]，价值为 c\[ i \]。现有一个容量为V的背包 (背包的最大承重为V)，问如何选取物品放入背包，使得背包内

小灰灰/ 2023年07月19日 10:34/ 0 赞/ 165 阅读

相关动态规划-背包问题(01背包、完全背包、多重背包)

背包问题 0/1背包原理输出方案例题HDU-2602 空间优化-滚动数组完全背包转

港控/mmm°/ 2023年02月28日 05:52/ 0 赞/ 157 阅读

相关背包问题详解：01背包、完全背包、多重背包

参考链接： 1. [http://www.cnblogs.com/fengty90/p/3768845.html][http_www.cnblogs.com_fengty9

蔚落/ 2022年09月30日 00:54/ 0 赞/ 406 阅读

相关背包问题(0-1背包、完全背包、多重背包)详解

背包问题一个背包总容量为V, 现在有N个物品, 第i个物品容量为weight\[i\], 价值为value\[i\], 现在往背包里面装东西, 怎样装才能使背包内物品总

柔情只为你懂/ 2022年06月08日 00:59/ 0 赞/ 467 阅读

相关算法——背包问题 01背包+完全背包+多重背包

01背包：https://biancheng.love/problem/51/index 有n 种不同的物品，每个物品有两个属性，weight重量，value 价值，现在给一

ゞ浴缸里的玫瑰/ 2022年06月06日 10:41/ 0 赞/ 452 阅读

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

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

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

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

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

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