「多重背包java」多重背包Java
本篇文章给大家谈谈多重背包java，以及多重背包Java对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
Pascal语言在什么软件上编写？我是一点都不知道，比较菜鸟。。一直有个问题想问，JAVA和Pascal在什么上编
我是一个搞NOIP竞赛的人 也搞过一点开发，你可以听听我的意见（全手打的，很累啊）
我学的就是Pascal语言，面向过程，用的是Free Pascal
如果是面向对象，就用Delphi
至于Java的编译器，可以试试NetBeans或者sun公司的jdk
像C也有面向过程和面向对象
面向过程是GCC
面向对象就是VC之类的了
Pascal的确是一个起步很好的语言，一开始就学C或C++会很累的
语言一般分3种：机器语言 汇编语言 高级语言
机器语言：能直接被CPU执行，效率极高，但是可移植性极差（换台电脑可能就不行了），写起来也很麻烦
汇编语言：不能直接被CPU执行，加入了一些人性化的东西，如加法用ADD、减法用SUB，但还是很麻烦
高级语言：效率最低，但是很人性化，可移植性很强 像Pascal C C++ JAVA都是高级语言
高级语言不能直接被计算机执行，所以就需要编译器来帮忙，把这些语句翻译一下，让CPU能执行
高级语言执行方式分两种：解释执行和编译执行
解释执行：编译器运行一句翻译一句，调试的时候就是这样的
编译执行：编译器将源文件编译成.exe的可执行文件，然后执行
像Free Pascal、Delphi、VB、VC这种，都是IDE
不仅可以编辑源代码，编译源代码，还可以调试程序等等
要学好编程，个人觉得分三块（把我下面讲的东西全学透，要1-2年）
①语法：学好语法是基础！学好了语法，才知道语言如何使用，这个不用我说吧
②数据结构（数据结构是脱离语言的，也就是说这些数据结构每个语言都好实现）：这是一个很抽象的东西，有 线性表、栈、队列、堆、数、图、串、集合 等等。
分为4种：线性结构（一对一，如 栈、队列）、树形结构（一对多，如 树）、离型结构（没有连接）、网状结构（多对多，如 图）
像栈就是一种FILO表，只运行在一头进行输入输出操作，应用在 表达式求值、撤销恢复操作上面
队列是FIFO表，允许在一头进行插入操作，另一头错删除操作
树 就复杂了 树和二叉树是两种概念，具体的自己去看书吧
二叉树有许多特殊形态，如满二叉树 完全二叉树 哈夫曼树 最优二叉树（哈夫曼树不等于最有二叉树！这点有许多人弄错。因为哈夫曼树不一定是二叉的）
二叉树的三种遍历方式一定要会：前序遍历（也称先根遍历）根左右， 中序遍历（也称中根遍历）左根右， 后序遍历（也称后根遍历）左右根
图就更复杂了，分 连通与不连通 带权与不带权 有向与无向，所以就有了 （不）连通有（无）向（不）带权图这种说法 还有什么强连通图，弱连通图的，自己看书吧！
③算法（算法是脱离语言的，也就是说这些算法每个语言都好写）：
1.低级算法（立意上的，就像初等数学和高等数学）：穷搜、深度优先搜索（DFS）、广度优先搜索（BFS，也称宽度优先搜索），是三种不同的遍历方式
2.高级算法:贪心，分支，动态规划（DP）。其他两个不介绍了，就介绍一下动态规划吧！
动态规划：记忆化搜索，利用以前搜索留下的数据，加快解决多阶段决策最优化问题的速度。要能动态规划，问题必须满足两个条件（我背了好长时间才背出来）
①：最优化原理（也称最优性原理）：无论过去的状态或决策如何，对于当前的决策所形成的状态而言，余下的诸决策必须构成最优策略。
②：无后效性：一旦一个状态的决策确定，则此后过程的演变不再受此前各状态及决策的影响，当前状态时此前历史的完整总结，此前历史只能通过当前状态去影响过程未来的演变。
学DP一般从背包开始，背包一共有8个：01背包、完全背包、多重背包、混合三种背包、二维费用背包、分组背包、有依赖的背包、泛化物品背包。
然后再学树形动态规划
还有排序算法：冒泡排序，选择排序，插入排序，快速排序，堆排序，希尔排序，基数排序，序数排序，桶排序，鸽巢排序，二叉树排序（应用二叉排序树），鸡尾酒排序（就是双向冒泡，在一次初赛的完善程序里出现过）
还有数论算法（不展开介绍了）
图论算法：
最短路（顾名思义，就是一个点到另一个点的最短路程）：迪杰斯特拉（Dijkstra）、弗洛伊德（Floyd）、SPFA（国人设计的，很不错）等等 还会要解决SPFA的负权回路问题 这几个算法都是解决单源最短路径问题的，就是一个点到所有点的最短路)
最小生成树（应用在无向连通图中，就是拿掉一些边，在保证图连通的情况下，使得剩下的边权值之和最小）：普利姆（Prim）、克鲁斯卡尔（Kruskal）
关键路径（在生产生活中应用很广，注意关键路径之前一定要拓扑一次！）、拓扑排序（可用于是否有环路的检测）、网络流等等
如果以上你都会了，那么恭喜你，你已经可以算是一名初级程序员了！
可以继续学 双向深搜、双向广搜、周界搜索、迭代加深搜索、迭代加宽搜索、A*广度优先启发搜索、A*迭代加深搜索 等高级的算法。
单调队列怎么用java实现
单调队列是一种严格单调的队列，可以单调递增，也可以单调递减。队首位置保存的是最优解，第二个位置保存的是次优解，ect。。。
单调队列可以有两个操作：
1、插入一个新的元素，该元素从队尾开始向队首进行搜索，找到合适的位置插入之，如果该位置原本有元素，则替换它。
2、在过程中从队首删除不符合当前要求的元素。
单调队列实现起来可简单，可复杂。简单的一个数组，一个head，一个tail指针就搞定。复杂的用双向链表实现。
用处：
1、保存最优解，次优解，ect。
2、利用单调队列对dp方程进行优化，可将O(n)复杂度降至O(1)。也就是说，将原本会超时的N维dp降优化至N-1维，以求通过。这也是我想记录的重点
是不是任何DP都可以利用单调队列进行优化呢？答案是否定的。
记住！只有形如 dp[i]=max/min (f[k]) + g[i] （ki g[i]是与k无关的变量）才能用到单调队列进行优化。
优化的对象就是f[k]。
通过例题来加深感受
我要长高
Description
韩父有N个儿子，分别是韩一，韩二…韩N。由于韩家演技功底深厚，加上他们间的密切配合，演出获得了巨大成功，票房甚至高达2000万。舟子是名很有威望的公知，可是他表面上两袖清风实则内心阴暗，看到韩家红红火火，嫉妒心遂起，便发微薄调侃韩二们站成一列时身高参差不齐。由于舟子的影响力，随口一句便会造成韩家的巨大损失，具体亏损是这样计算的，韩一，韩二…韩N站成一排，损失即为C*（韩i与韩i+1的高度差（1=iN））之和，搞不好连女儿都赔了.韩父苦苦思索，决定给韩子们内增高（注意韩子们变矮是不科学的只能增高或什么也不做），增高1cm是很容易的，可是增高10cm花费就很大了，对任意韩i，增高Hcm的花费是H^2.请你帮助韩父让韩家损失最小。
Input
有若干组数据，一直处理到文件结束。 每组数据第一行为两个整数：韩子数量N(1=N=50000)和舟子系数C(1=C=100) 接下来N行分别是韩i的高度(1=hi=100)。
首先建立方程，很容易想到的是，dp[i][j]表示第 i 个儿子身高为 j 的最低花费。分析题目很容易知道，当前儿子的身高花费只由前一个儿子影响。因此，
dp[i][j]=min(dp[i-1][k] + abs(j-k)*C + (x[i]-j)*(x[i]-j))；其中x[i]是第i个儿子原本的身高
我们分析一下复杂度。
首先有N个儿子，这需要一个循环。再者，每个儿子有0到100的身高，这也需要一维。再再者，0到100的每一个身高都可以有前一位儿子的身高0到100递推而来。
所以朴素算法的时间复杂度是O(n^3)。题目只给两秒，难以接受！
分析方程：
当第 i 个儿子的身高比第 i-1 个儿子的身高要高时，
dp[i][j]=min(dp[i-1][k] + j*C-k*C + X); ( k=j ) 其中 X=(x[i]-j)*(x[i]-j)。
当第 i 个儿子的身高比第 i-1 个儿子的身高要矮时，
dp[i][j]=min(dp[i-1][k] - j*C+k*C + X); ( k=j )
对第一个个方程，我们令 f[i-1][k]=dp[i-1][k]-k*C, g[i][j]=j*C+X; 于是 dp[i][j] = min (f[i-1][k])+ g[i][j]。转化成这样的形式，我们就可以用单调队列进行优化了。
第二个方程同理。
接下来便是如何实现，实现起来有点技巧。具体见下
View Code
还有一个比较适合理解该优化方法的题目是HDU 3401
大概题目便是：一个人知道接下来T天的股市行情，想知道最终他能赚到多少钱。
构造状态dp[i][j]表示第i 天拥有 j只股票的时候，赚了多少钱
状态转移有：
1、从前一天不买不卖:
dp[i][j]=max(dp[i-1][j],dp[i][j])
2、从前i-W-1天买进一些股:
dp[i][j]=max(dp[i-W-1][k]-(j-k)*AP[i],dp[i][j])
3、从i-W-1天卖掉一些股:
dp[i][j]=max(dp[i-W-1][k]+(k-j)*BP[i],dp[i][j])
这里需要解释一下为什么只考虑第i-W-1天的买入卖出情况即可。想想看，i-W-2天是不是可以通过不买不卖将自己的最优状态转移到第i-W-1天？以此类推，之前的都不需要考虑了，只考虑都i-W-1天的情况即可。
对买入股票的情况进行分析，转化成适合单调队列优化的方程形式
dp[i][j]=max(dp[i-W-1][k]+k*AP[i])-j*AP[i]。令f[i-W-1][k]=dp[i-W-1][k]+k*AP[i]，则dp[i][j]=max(f[i-W-1][k]) - j*AP[i]。
这便可以用单调队列进行优化了。卖股的情况类似分析。
View Code
最后再说一个应用，用单调队列来优化多重背包问题 hdu 2191
如果有n个物品，每个物品的价格是w，重量是c，且每个物品的数量是k，那么用这样的一些物品去填满一个容量为m的背包，使得得到的背包价值最大化，这样的问题就是多重背包问题。
对于多重背包的问题，有一种优化的方法是使用二进制优化，这种优化的方法时间复杂度是O(m*∑log k[i])，具体可以见
而利用单调队列的优化，复杂度是O(mn)
首先，对于第i件物品，如果已知体积为V，价值为W，数量为K，那么可以按照V的余数，将当前的体积J分成V组(0,1,....V-1)。
对于任意一组，可以得到转移方程：f[i*V+c]=f[k*V+c]+(i-k)*W，其中c是V组分组中的任意一个
令f[i*V+c]=dp[i]，那么就得到dp[i]=dp[k]+(i-k)*W (k=i-K)
将dp[k]-k*W看做是优化函数，那么就可以运用单调队列来优化了
Java 多重for 参数
你把j的赋值写在外面，经过第一轮循环后j已经等于10了，进不了内循环所以不会输出
public static void main(String[] args) {
int i=0,j=0;//这个j应该在内循环条件中来赋初值，变量作用域要看清楚
for (; i 10; i++) {
System.out.println(i+"--"+j);
/*
0--0
0--0
0--1
0--2
0--3
0--4
0--5
0--6
0--7
0--8
0--9
1--10
2--10
3--10
4--10
5--10
6--10
7--10
8--10
9--10
*/
for (; j 10; j++) {//j应该给到这来
System.out.println(i + "--" + j);
}
}
}
多重背包java的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于多重背包Java、多重背包java的信息别忘了在本站进行查找喔。