- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
是否有一种算法可以确定背包的确切重量为 W? IE。这就像正常的 0/1 背包问题,n 件元素的重量分别为 w_i 和值(value) v_i。最大化所有元素的值(value),但是背包中元素的总重量需要恰好为W!
我知道“正常的”0/1 背包算法,但这也可能返回重量更轻但值(value)更高的背包。我想找到最高值但精确的 W 权重。
这是我的 0/1 背包实现:
public class KnapSackTest {
public static void main(String[] args) {
int[] w = new int[] {4, 1, 5, 8, 3, 9, 2}; //weights
int[] v = new int[] {2, 12, 8, 9, 3, 4, 3}; //values
int n = w.length;
int W = 15; // W (max weight)
int[][] DP = new int[n+1][W+1];
for(int i = 1; i < n+1; i++) {
for(int j = 0; j < W+1; j++) {
if(i == 0 || j == 0) {
DP[i][j] = 0;
} else if (j - w[i-1] >= 0) {
DP[i][j] = Math.max(DP[i-1][j], DP[i-1][j - w[i-1]] + v[i-1]);
} else {
DP[i][j] = DP[i-1][j];
}
}
}
System.out.println("Result: " + DP[n][W]);
}
}
这给了我:
Result: 29
(请问我的问题有什么不清楚的!)
最佳答案
实际上,正如@Shinchan 在评论中发现的那样,接受的答案是错误的。
您只需更改初始 dp
状态即可获得精确重量的背包,而不是算法本身。
初始化,而不是:
if(i == 0 || j == 0) {
DP[i][j] = 0;
}
应该是:
if (j == 0) {
DP[i][j] = 0;
} else if (i == 0 && j > 0) { // obviously `&& j > 0` is not needed, but for clarity
DP[i][j] = -inf;
}
其余的保持在你的问题中。
关于java - 背包但确切重量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47608725/
我有以下查询: select ema.es_symbol as symbol, ema.score as score, ema.weight as weight, rsi.relative_stren
我有一个 ms-sql 表,看起来像这样(重量 = kg)。 我希望能够计算给定标识符所需的箱子数量和每个箱子的重量。一个盒子最多可以容纳 30 公斤。该标识符的所有项目都可以在一个框中混合。我仅限于
我正在尝试通过 PHP 将重量分配给卡车。 条件 卡车可以有不同的尺寸 可设置单辆或多辆 卡车越少越好 我有这个 class VehicleCalculation { /** * @var
如何在这段代码中引用石头的重量,以便我可以在unlockChest方法中使用它?我基本上试图将用户从对象 new Stone()) 输入的权重相加,因此它 == 组合了用户在 Chest() 构造函数
我在线性布局中使用表格布局,第一行结果很好,但连续的行完全错误,尽管设置了它们。我不确定这是否是我正在运行的 Android Studio 版本的问题,或者它是否不适用于 kotlin ...有什么办
我在平衡方面遇到了麻烦。我觉得我在这里遗漏了一些东西.. 这个问题等同于以下情况: table 上散布着各种质量的砝码。 你手里拿着几个不同质量的砝码。 如果 table 上有一组重量与您手中的重量相
我已经在 YOLOv3 中进行了超过 3 个类别的自定义检测,但是检测结果不准确,所以我想用更多图像重新训练我的自定义 YOLO 权重,但是 当我用新图像运行它时,它立即完成,我做错了什么? 这是我如
所以我需要分割字符串: Laundry Detergent 2X Ultra Free Clear 50
我使用 ClientBundle 和 CssResource 接口(interface)。所有适用于类的样式都有效: 在 CSS 中:.dialogVPanel { margin: 5px;} 在界面
我几乎是编程新手,所以这可能看起来是一个非常愚蠢的问题,我已经尝试这样做有一段时间了,但无法理解它。 但是我想知道 JList 对象是否可以存储多个值,因此当我单击列表中的对象时,不同的值(例如价格、
我想创建具有相同宽度并被拉伸(stretch)以(匹配)父按钮的按钮。我需要以编程方式来完成它。首先,我创建了一个所需状态的布局草稿(只关注按钮的绿线):
我正在尝试在 iOS 中模拟 Android android:layout_weight="1" 中的属性。 我有一个带有 7 个按钮的 View ,我希望它们都具有相同的宽度和相同的边距。在 And
我想知道使用 XmlDocument 类来处理小型 XML 文件的感觉。如果在加载XML文件的过程中,XmlDocument为所有的XML元素及其关系创建了一整套面向对象的结构,理论上对于小的xml文
给定 n 个无限容量的箱子,我想将 m 件元素装入其中(每个元素都有特定的重量),同时最小化最重箱子的重量。 这不是传统的垃圾箱包装/背包问题,其中垃圾箱的容量有限,而您试图尽量减少使用的垃圾箱数量;
过去几天我一直在学习 D3。我尝试将我所学到的所有内容简化为一个简单的 D3 示例,但我看到了标题中提到的错误。 我确信这很简单,我错过了什么? 代码: .node { fill: #c
我是一名优秀的程序员,十分优秀!