- Java 双重比较
- java - 比较器与 Apache BeanComparator
- Objective-C 完成 block 导致额外的方法调用?
- database - RESTful URI 是否应该公开数据库主键?
在 0/1 背包问题中,如果两个项目具有相同的值,我如何选择项目。应该选择权重较小的值,如何检查该条件?我有以下使用动态编程的功能。
static int[] knapsack(int maxWeight, double[] weight, double[] value, int n) {
//n = no. if items
int i, w;
double array[][] = new double[n + 1][maxWeight + 1];
for (i = 0; i <= n; i++) {
for (w = 0; w <= maxWeight; w++) {
if (i == 0 || w == 0)
array[i][w] = 0;
else if (weight[i - 1] <= w)
array[i][w] = max(value[i - 1] + array[i - 1][(w -(int) weight[i - 1])], array[i - 1][w]);
else
array[i][w] = array[i - 1][w];
if (i != 0 || w != 0)
System.out.print(array[i][w] + "\t");
}
System.out.println();
}
int[] selected = new int[n + 1];
for (int j = n, wt = maxWeight; j > 0; j--) {
if (array[j][wt] != array[j - 1][wt]) {
if (array[j][wt] == array[j][wt - 1]) {
selected[j] = 0;
break;
}
selected[j] = 1;
wt = wt - (int) weight[j - 1];
}
else
selected[j] = 0;
}
/** Print finally selected items **/
System.out.println("\nItems selected : ");
for (int k = 1; k < n + 1; k++)
if (selected[k] == 1)
System.out.print(k +" ");
System.out.println();
return selected;
}
对于这种情况:(i,v): (4,45)(3,20)(5,30)(2,45) ,maxWeight = 5; 如果第 1 项和第 4 项具有相同的值,则应选择权重较小的第 4 项。我如何在上面的代码中实现这个条件。问题陈述:
Your goal is to determine which things to put into the package so that the total weight is less than or equal to the package limit and the total cost is as large as possible. You would prefer to send a package which weights less in case there is more than one package with the same price.
最佳答案
如果您的意思是通过最小化权重来最大化值(value)。你可以检查一下
令DP[i][j]为可获得的最大值!
W[i][j] 是要使用的最小权重!!
然后,
if(Current Weight > Element's Weight)
{
if(DP[i-1][j-Weight[i]]+Value[i]>DP[i-1][j]){
DP[i][j]=DP[i-1][j-Weight[i]]+Value[i];
Weight[i][j]= Weight[i-1][j-Weight[i]]+Value[i]
}
else if(DP[i-1][j-Weight[i]]+Value[i] < DP[i-1][j] ){
DP[i][j]=DP[i-1][j];
Weight[i][j]=Weight[i-1][j];
}
else{ //Note this is the tricky part elsewise the
//Above conditions are simple Knapsack conditions
DP[i][j]=DP[i-1][j]; //Both of them are equal We will get same Value . Thus we cannot maximise it in any other way!!
Weight[i][j]=minimum ( Weight[i-1][j] ,Weight[i-1][j-Weight[i]]+A[i]);
}
}
else
{
DP[i][j]=DP[i-1][j];
Weight[i][j]=Weight[i-1][j];
}
注意解决方案很简单,除非第一个 if 中的第三个条件!我们需要不惜一切代价最大化乐趣!所以我们不是在搞乱它!但是当两种情况的乐趣相同时,我们需要选择重量更轻的那个,否则我们最终会以相同的背包重量获得更多的重量!
我假设你知道背包 0/1 问题,这就是为什么我没有解释第一个和第二个条件!!
关于java - 选择 0/1 背包中的元素,其中两个元素具有相同的 yield |最大化值(value)和最小化重量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31482546/
是 if(a == 0 && b == 0 && c == 0) { return; } 一样 if(a == 0) { return; } if(b == 0) { return; } if(c =
我想做这样的事情: Class A Class B extends A Class C extends A B b = new B(); C c = new C(); b->setField("foo
我对 Mysql 世界很天真......:)我试图使用连接从表中查询, 我遇到结果集问题...表结构如下 下面... VIDEO_XXXXX | Field | Type
我最近问过关于从另一个类获取类的唯一实例的问题。 ( How to get specific instance of class from another class in Java? ) 所以,我正
假设我们有两种类型 using t1 = int*; using t2 = int*; 我知道 std::is_same::value会给我们true .什么是,或者是否有模板工具可以实现以下目标?
对于我的一个应用程序,我假设比较 2 个字符串的第一个字符比比较整个字符串是否相等要快。例如,如果我知道只有 2 个可能的字符串(在一组 n 字符串中)可以以相同的字母开头(比如说 'q'),如果是这
我想在我的NXP LPC11U37H主板(ARM Cortex-M0)上分析一些算法,因为我想知道执行特定算法需要多少个时钟周期。 我编写了这些简单的宏来进行一些分析: #define START_C
我在 Excel 中创建了一个宏,它将在 Excel 中复制一个表格,并将行除以我确定的特定数字(默认 = 500 行),并为宏创建的每个部门打开不同的工作表。 使用的代码是这样的: Sub Copy
我想根据第一个字典对第二个字典的值求和。如果我有字典 A 和 B。 A = {"Mark": ["a", "b", "c", "d"], "June": ["e", "a"], "John": ["a
当我这样做时 system()在 Perl 中调用,我通常根据 perldocs 检查返回码.嗯,我是这么想的。大部分时间 $rc!=0对我来说已经足够了。最近我在这里帮助了两个遇到问题的人syste
在我的进度条上,我试图让它检测 div 加载速度。 如果 div 加载速度很快,我想要实现的目标将很快达到 100%。但进度条的加载速度应该与 div 的加载速度一样快。 问题:如何让我的进度条加载
当我获得与本地时间相同的时间戳时,firebase 生成的服务器时间戳是否会自动转换为本地时间,或者我错过了什么? _firestore.collection("9213903123").docume
根据the original OWL definition of OWL DL ,我们不能为类和个体赋予相同的名称(这是 OWL DL 和 OWL Full 之间的明显区别)。 "Punning" i
我有两个输入复选框: 尝试使用 jQuery 来允许两个输入的行为相同。如果选中第一个复选框,则选中第二个复选框。如果未检查第 1 个,则不会检查第 2 个。反之亦然。 我有代码: $('inpu
可以从不同系统编译两个相同的java文件,但它们都有相同的内容操作系统(Windows 7),会生成不同的.class文件(大小)? 最佳答案 是的,您可以检查是否有不同版本的JDK(Java Dev
我正在清理另一个人的正则表达式,他们目前所有的都以结尾 .*$ 那么下面的不是完全一样吗? .* 最佳答案 .*将尽可能匹配,但默认情况下为 .不匹配换行符。如果您要匹配的文本有换行符并且您处于 MU
我使用 Pick ,但是如何编写可以选择多个字段的通用PickMulti呢? interface MyInterface { a: number, b: number, c: number
我有一个 SQL 数据库服务器和 2 个具有相同结构和数据的数据库。我在 2 个数据库中运行相同的 sql 查询,其中一个需要更长的时间,而另一个在不到 50% 的时间内完成。他们都有不同的执行计划。
我需要你的帮助,我有一个包含两列的表,一个 id 和 numpos,我希望 id 和 numops 具有相同的结果。 例子: $cnx = mysql_connect( "localhost", "r
如何将相同的列(在本例中按“级别”排序)放在一起?我正在做一个高分,我从我的数据库中按级别列出它们。如果他们处于同一级别,我希望他们具有相同的 ID。 但是我不想在别人身上显示ID。只有第一个。这是一
我是一名优秀的程序员,十分优秀!