package cn.gao.algorithm2.service;
public class Test7 {
/**
* @param args
* 动态规划问题,0-1背包问题
* f[i,j]表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值
* f[i,j]=max{f[i-1,j-Wi]+Pi (j>=Wi), f[i-1,j]}
* 核心思想是:对于第N件物品放或者不放;
*/
public static int f(int a[],int b[],int i,int j)/*参数依次为物品重量数组,物品价值数组,物品的数量,剩余背包的重量*/
{
if(i==1)
{
if(j>=a[i-1])
{
return b[i-1];
}
else
{
return 0;
}
}
if(a[i-1]>j)/*第i个物品大于背包重量,直接丢弃*/
{
return f(a,b,i-1,j);
}
else{/*在可选取第i件物品时候,取 选和不选 这二种情况的最大值*/
return f(a,b,i-1,j-a[i-1])+b[i-1]>f(a,b,i-1,j)?f(a,b,i-1,j-a[i-1])+b[i-1]:f(a,b,i-1,j);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]={1,3,5,7,9};
int b[]={8,6,4,2,1};
int weigth=15;
System.out.println(f(a,b,a.length,weigth));
}
}
分享到:
相关推荐
如题,动态规划法求解0-1背包问题实验报告 大二算法作业 使用java语言实现 内容框架:问题描述 思路分析 实例分析 实验原码及运行结果 实验心得
算法实验中用动态规划法解0-1背包问题,这里提供了源代码,仅供参考
背包问题是一个经典的动态规划模型。它既简单形象容易理解,又在某种程度上能够揭示动态规划的本质,不少教材都把它作为动态规划部分的第一道例题。
计算机算法设计与分析动态规划法求解0-1背包问题的改进算法完整解释
利用动态规划方法求解经典0-1背包问题,仅供参考,欢迎指正
基于MATLAB平台,用动态规划法解决0-1背包问题,较为简单。参数分别为[物品重量,物品价值,背包容量,背包价值]
北京工业大学--算法作业2--动态规划算法实现0-1背包问题---Java代码 利用动态规划算法实现0-1背包问题或装配线调度问题。(二选一) 要求测试数据以文本文件的形式存储, 即所有的数据由文本文件读入。 利用动态...
0-1背包问题 动态规划源码0-1背包问题 动态规划源码0-1背包问题 动态规划源码0-1背包问题 动态规划源码0-1背包问题 动态规划源码0-1背包问题 动态规划源码0-1背包问题 动态规划源码
这个是动态规划之跳跃点0-1背包问题,如果只是想要动态规划0-1背包问题求解代码,请到主页查看。18级学姐自主完成的算法作业,呕心沥血,基于四舍五入等于0基础的python实现,如果在语言规范上存在不足,那就。就憋...
提供0-1背包问题c++代码,实现功能如下: /**输入参数: * @param m 表示背包的最大容量 * @param n 表示商品个数 * @param a[] 每个商品的容量 * @param p[] 每个商品的价值 */ /**输出: 求最大商品value*/
c++实现的0-1背包问题 算法设计的动态规划问题
C++ 动态规划算法实现0-1背包问题 包含了代码、算法分析、测试文件和结果,非常详尽,值得拥有!
0/1背包问题是学习动态规划算法最经典的例子 Java代码实现0/1背包问题 代码里有详细的注释,比较好理解
背包的重量有限,每次只可取一种商品。利用动态规划实现所选商品总价值的最大值。
0-1背包问题 动态规划 分支限界 回溯 贪心四种方法
本资源包含了0-1背包问题的最佳所有解法,其中包括动态规划算法,回溯法算法,分支限界算法和贪心算法。包含源代码。
解0-1背包问题的动态规划算法及其两次改进,许薇,周继鹏,给出了用动态规划算法解决0-1背包问题的证明,分析了动态规划算法解决0-1背包问题的不足和性能。然后,针对用该动态规划算法解决0-1
动态规划 0-1背包问题问题描述:有 n 件物品x1, x2, …, xn , 每件物品有一个价值和一个重量,分别记为: v1,v2, …vn w1,w2, …wn 其中所有的 wi 均为整数。 现有一个背包,其最大载重量为m,要求从这n件物品中任...