算法-背包问题 VI(动态规划)

今天做了一道背包问题的变种问题,这个问题还是用动态规划来做,但是做法上跟原来的背包问题有很大的区别。

题意:

给出一个都是正整数的数组 nums,其中没有重复的数。从中找出所有的和为
 target 的组合个数。

样例:

给出 nums = [1, 2, 4], target = 4
可能的所有组合有:

[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]
[4]

返回 6

1.最简单的方法--深搜(超时)

看到这种问题,特别是要求我们将所有的情况计算出来,我们首先想到的是就是深搜。这个题用深搜做时非常的简单,但是不可避免的就是超时。

代码:

 1     private static int count = 0;
 2
 3     public static int backPackVI(int[] nums, int target) {
 4         dfs(nums, new int[target], 0, 0, target);
 5         return count;
 6     }
 7     /**
 8      *
 9      * @param nums  原来的数组
10      * @param select  选择的数字组成的数组,为什么它的长度为target,那么因为要想和等于target,最长的情况是全部是1
11      * 所以最长为target
12      * @param i  记录开始填充select数组里面的第i个位置了
13      * @param sum  //select数组的和
14      * @param target  //目标值
15      */
16     private static void dfs(int nums[], int select[], int i, int sum, int target) {
17         if (sum == target) {
18             count++;
19         } else {
20             //这里一定要记住i必须小于select的长度
21             for (int j = 0; j < nums.length && i < select.length; j++) {
22                 if (sum + nums[j] <= target) {
23                     select[i] = nums[j];
24                     dfs(nums, select, i + 1, sum + nums[j], target);
25                 }
26
27             }
28         }
29     }

2.动态规划

动态规划第一步的操作就是填表,所以,我们要想推导出动态规划的方程,必须先填表(填表的假设条件的设置尤为重要)。如图所示:

代码:

 1     public static int backPackVI(int[] nums, int target) {
 2         //dp数组,用来记录在每一种情况下,不同数字装的所有情况个数
 3         int dp[][] = new int[target + 1][nums.length];
 4         //不同target下,所有情况的个数
 5         int b[]  = new int[target+ 1];
 6         for(int i = 0; i < dp.length; i++){
 7             Arrays.fill(dp[i], 0);
 8         }
 9         Arrays.fill(b, 0);
10         for(int i = 1; i < dp.length; i++)
11         {
12             for(int j = 0; j < nums.length; j++){
13                 //当当前的数字大于当前的target,肯定不能装进去
14                 if(nums[j] > i){
15                     continue;
16                 }
17                 //dp方程
18                 dp[i][j] = b[i - nums[j]];
19                 //当当前的数字恰好等于target时,将dp的值更新,正确值应该为1,先前为0
20                 if(nums[j] == i){
21                     dp[i][j] = 1;
22                 }
23             }
24             //初始化一下b[i],理论上可以不用初始化,为了保证正确性
25             b[i] = 0;
26             //更新b[i]的值
27             for(int j = 0; j < nums.length; j++){
28                 b[i] += dp[i][j];
29             }
30         }
31         int sum = 0;
32         for(int i = 0; i < nums.length; i++){
33             sum += dp[target][i];
34         }
35         return sum;
36     }
时间: 09-09

算法-背包问题 VI(动态规划)的相关文章

编程算法 - 背包问题(递归) 代码(C)

背包问题(递归) 代码(C) 本文地址: http://blog.csdn.net/caroline_wendy 题目: 有n个重量和价值分别为w,v的物品, 从这些物品中挑选出总重量不超过W的物品, 求所有挑选方案中价值总和的最大值. 即经典动态规划问题. 可以使用深度优先搜索, 把每个部分都遍历到, 选取最优解, 但不是最好的方法. 代码: /* * main.cpp * * Created on: 2014.7.17 * Author: spike */ /*eclipse cdt, gc

0-1背包问题(动态规划)

<span style="font-size:18px;">#include<iostream> #include<vector> #include<iterator> #include<algorithm> #include<string> using namespace std; /* *0-1背包问题(动态规划) */ vector<vector<int>> values;//valu

算法导论 之 动态规划 - 矩阵链相乘

1 引言 在大学期间,我们学过高等数学中的线性规划,其中有关于矩阵相乘的章节:只有当矩阵A的列数与矩阵B的行数相等时,A×B才有意义.一个m×n的矩阵A(m,n)左乘一个n×p的矩阵B(n,p),会得到一个m×p的矩阵C(m,p).矩阵乘法满足结合律,但不满足交换律. 假设现要计算A×B×C×D的值,因矩阵乘法满足结合律,不满足交换律,即:A.B.C.D相邻成员的相乘顺序不会影响到最终的计算结果,比如: A×(B×(C×D)).A×((B×C)×D).(A×B)×(C×D).A×(B×C)×D.

01背包问题【动态规划】

问题: 假设有n个物品,每个物品都是有重量的,同时每个物品也是有价值的,要求把这些物品放到一个背包中,这个背包的载重量是有限制的,怎么使得背包里面的物品总价值最大? 符号表示: N:物品个数 W:背包载重量 w[i]:物品i的重量(1<i<=N) v[i]:物品i的价值(1<i<=N) c[i, j]:到物品i为止,背包重量限制为j的最优解(1<i<=N, 1<j<=W) 分析: 最优解结构:对于物品i,只有两种情况,放入或不放入.假设物品i放入了是最优解的

《背包问题》 动态规划

问题描述: 一切都要从一则故事说起. 话说有一哥们去森林里玩发现了一堆宝石,他数了数,一共有n个. 但他身上能装宝石的就只有一个背包,背包的容量为C.这哥们把n个宝石排成一排并编上号: 0,1,2,-,n-1.第i个宝石对应的体积和价值分别为V[i]和W[i] .排好后这哥们开始思考: 背包总共也就只能装下体积为C的东西,那我要装下哪些宝石才能让我获得最大的利益呢? 思路分析: 这是动态规划中的经典问题. 核心状态为:dp[i][j] 表示将i件宝物放入容量为j的背包中可以得到的最大价值. 状态

编程算法 - 背包问题(记忆化搜索) 代码(C)

背包问题(记忆化搜索) 代码(C) 本文地址: http://blog.csdn.net/caroline_wendy 题目参考: http://blog.csdn.net/caroline_wendy/article/details/37912949 使用记忆化搜索, 需要存储每组的值, 下次不需要进行继续迭代, 可以降低至时间复杂度O(nW). 代码: /* * main.cpp * * Created on: 2014.7.17 * Author: spike */ /*eclipse c

十:贪心算法-背包问题

问题:贪心算法-背包问题题目描述有一背包空间为m,现有n个物体,他们的重量为w[i],价值为v[i].应该如何选择装入背包的物品,使其装入背包的物品总价值最大?(因为采用贪心算法,最终的结果不一定最优,但应该是接近于最优.提示:本题所选的方法为每次选取单位价值最高的物品)输入第一行分别为背包的空间m和物品数量n接下来有n行每行分别为物体的w[i]和价值v[i]输出一个整数样例输入30 328 3012 2014 20样例输出 40 1 #include<stdio.h> 2 int k=0;

《Java算法》Java动态规划

1. 算法思想: 动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法.动态规划实际上是一类题目的总称,并不是指某个固定的算法.动态规划的意义就是通过采用递推(或者分而治之)的策略,通过解决大问题的子问题从而解决整体的做法.动态规划的核心思想是巧妙的将问题拆分成多个子问题,通过计算子问题而得到整体问题的解.而子问题又可以拆分成更多的子问题,从而用类似递推迭代的方法解决要求的问题. 2. 应用场景:适用动态规划的问

01背包问题的动态规划算法

01背包问题我最初学会的解法是回溯法,第一反应并不是用动态规划算法去解答.原因是学习动态规划算法的时候,矩阵连乘.最长公共子串等问题很容易将问题离散化成规模不同的子问题,比较好理解,而对于01背包问题则不容易想到将背包容量离散化抽象出子问题,从情感上先入为主也误以为动态规划算法不是解决01背包问题的好方法,实际上并不是这样的.另外,动态规划算法不对子问题进行重复计算,但是要自底向上将所有子问题都计算一遍,直到计算出最终问题的结果也就是我们要的答案,有点像爬山的感觉. 问题描述:给定n种物品和一背