01背包问题是动态规划中很基础也很经典的问题,给大家推荐一个网址(背包 九讲),里面讲的很详细。
http://love-oriented.com/pack/P01.html
按我的理解,01背包就是一种特定价值的物品放到背包中去,要么放,要么不放。循环中嵌套的循环用逆序,复杂度为O(N*W)
POJ3624原题为
http://poj.org/problem?id=3624
import java.util.Scanner;
public class Main
{
Scanner scan=new Scanner(System.in);
/*01背包的状态转移方程为(二维)
* f[i][w]=max{f[i-1][w],f[i-1][w-w[i]]+v[i]};
*/
int N=scan.nextInt(); //N个物品,总重量W
int W=scan.nextInt();
int[] w=new int[N+1]; //每个物品的重量
int[] v=new int[N+1]; //每个物品的价值
int dp[]=new int[12881];
void ZOP()
{
for(int i=1;i<=N;i++)
{
for(int j=W;j>=w[i];j--) //逆序输出
{
dp[j]=Math.max(dp[j-w[i]]+v[i],dp[j]);
}
}
System.out.println(dp[W]);
}
void run()
{
for(int i=1;i<=N;i++)
{
w[i]=scan.nextInt();
v[i]=scan.nextInt();
}
ZOP();
}
public static void main(String[] args) throws Exception
{
new Main().run();
}
}
分享到:
相关推荐
动态规划 01背包问题 POJ3624可以AC
在给出的文件列表中,“POJ1014-Dividing【多重背包+二进制优化】.cpp”和“POJ1014-Dividing【DFS】.cpp”很可能是两份不同的C++代码实现,分别展示了如何结合多重背包和二进制优化以及如何利用DFS来解决问题。...
* 背包问题:背包问题是指解决问题的背包问题算法,如 poj1837、poj1276。 * 型如下表的简单 DP:型如下表的简单 DP 是指解决问题的简单 DP 算法,如 poj3267、poj1836、poj1260、poj2533。 * 计算几何学:计算几何...
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
* 背包问题:例如 poj1837、poj1276。 * 类型 DP:例如 poj3267、poj1836、poj1260、poj2533。 中级 1. 基本算法: * C++的标准模版库的应用:例如 poj3096、poj3007。 * 较为复杂的模拟题的训练:例如 poj...
例如,poj1328和poj2109就是典型的贪心问题。贪心算法的关键在于正确性证明,确保每一步的局部最优能够导向全局最优。 #### 分治法与递归 分治法是将大问题分解成若干个子问题,递归地求解这些子问题,然后将子问题...
3. **贪心算法**:通过局部最优选择来达到全局最优解的方法,如背包问题(poj3295)。 4. **动态规划**:通过分解问题为更小的子问题来解决复杂问题,如斐波那契数列(poj1068, poj2632, poj1573, poj2993, poj2996...
经典的0-1背包问题. 适合新手学习. 原题网址:http://poj.grids.cn/problem?id=2773
- 背包问题:如`poj1837, poj1276`。 - 简单DP:如`poj3267, poj1836`。 - **数学** - 组合数学:如`POJ3252, poj1850`。 - 数论:如`poj2635, poj3292`。 #### 第二阶段中级训练计划 #### 第3周至第4周(共...
01背包问题是最经典的动态规划问题之一,问题描述为:给定一组物品,每种物品都有自己的重量和价值,在限定的总重量内,选择其中一些装入背包,使得背包内物品的总价值最大。而多重背包问题是指有N种物品,每种物品...
- (poj3267, poj1836, poj1260, poj2533):零一背包、完全背包等问题的解决方案。 3. **二维动态规划**: - (poj3176, poj1080, poj1159):多维状态转移方程的应用。 ### 五、组合数学 1. **排列组合基础**: ...
动态规划则常用于解决背包问题、最长公共子序列等复杂问题;贪心算法常常用于解决最优调度、最小花费等问题;排序算法如快速排序、归并排序等也是常考内容;搜索算法如深度优先搜索、广度优先搜索和A*搜索等在解决...
- **背包问题**:如poj1837,解决有限资源下的最优化问题。 - **表格型DP**:如poj3267,通过状态转移矩阵求解问题。 6. **数学**: - **组合数学**:包括计数原理、排列组合以及递推关系,如poj3252。 - **...
- POJ 1130 - The Sultan's Successors(背包问题变体) **相关知识点**: - 状态定义与转移方程的建立 - 多维DP与一维DP的转换技巧 - DP算法的时间复杂度分析 - 背包问题的不同类型及其解法 #### 四、总结 通过...
在编程竞赛中,动态规划通常被用来解决如背包问题、最长公共子序列、最短路径等问题。 对于POJ 1170的具体问题,由于没有给出详细描述,我们可以进行一般性的动态规划知识讲解。动态规划问题通常分为以下几步: 1....
晒代码之二——多重背包(POJ1276)
012背包问题是一种特殊的背包问题,物品有三种选择:不选、选一次或选两次。这类问题可以转化为普通背包问题进行解决,但需要更复杂的定义状态和转移方程。 #### 三、线性的动态规划问题 ##### 1. 积木游戏问题 ...
动态规划题目通常要求求解最优解,例如背包问题、最长公共子序列等问题。例如,题目poj3267和poj1836就属于动态规划问题,其中poj1836需要通过动态规划找到最优的编辑距离。 ### 5. 数学算法 数学算法涵盖代数、...
这些题目覆盖了基础的动态规划问题,如背包问题、最长递增子序列、矩阵链乘法等。例如: - **1018**:“Falsecoin”——经典的0/1背包问题变种。 - **1178**:“Camelot”——涉及到最短路径问题的变体。 - **...
例如,在01 背包问题中,采用贪心算法可以选择当前最优的选择,以达到最大化的效果。 递归算法是一种常用的算法思想,递归算法的核心思想是将问题分解为更小的子问题,然后递归地解决这些子问题。例如,在树状数组...