我上周完成了这个任务,但找不到一个好的算法来解决这个问题.所以这里是描述:
您可以通过不将较大的立方体放置到较小的立方体上来构建具有建筑立方体的稳定塔,并且如果不将较硬的立方体放入较轻的立方体中.制作一个程序,为您提供具有n个立方体的最高塔.
输入:
在in.txt的第一行中有多维数据集的数量n(1 = <n = <1000).下面的n行包括两个正整数,一个立方体的边长和重量(它们都不高于2000)没有相似的立方体,其中sidelength和wieght是相同的
输出:
你必须把最高稳定塔的m号写入out.txt.进入第二行,您必须从塔底到顶部写入塔的序数m.根据塔的高度,我们指的是所有立方体的边长(而不是立方体的数量).如果有多个解决方案,您可以
为输入和输出提供您想要的任何示例:
输入:
5
10 3
20 5
15 6
15 1
10 2
和输出:
3
2 1 5
这里是程序的限制.时间限制:0.2秒.内存限制:16 Mb
我希望你能帮助我解决这个问题.thx所有的帮助
堆栈在n = 1000之前溢出.是因为对long []参数的引用,JVM感觉需要保持每个堆栈帧(疯狂猜测),还是我做错了什么？
public static void main(String[] args) {
long start = System.currentTimeMillis();
fibonacciMemoized(1000);
long end = System.currentTimeMillis();
System.out.println("\nTotal run time: " + (end-start));
}
public static void fibonacciMemoized(int n) {
long[] fibMemos = new long[n+1];
for (int i = 0; i < fibMemos.length; i++) {
fibMemos[i] = Long.MAX_VALUE;
}
long fibResult = fib(n, 1, 0, fibMemos);
System.out.println(fibResult);
}
public static long fib(int n, long fibAcc, long fibPrev, long[] fibMemos) {
if (fibMemos[n] != Long.MAX_VALUE){
return fibMemos[n];
} else …java stack-overflow tail-recursion memoization dynamic-programming
分而治之和动态编程的主要区别是什么？如果我们举一个例子,合并排序基本上是通过使用递归的分而治之来解决的.动态编程也是基于递归,而不是为什么Merge sort被认为是动态编程的一个例子呢？
我有一个与0-1背包类似的问题。
我试图做的修改是获取所选对象的列表，而不是成本。我尝试使用以下代码：
public static int fillPackage(double weight,ArrayList<Item> item, int n) {
//base case
if(n == 0 || weight == 0)
return 0;
if(item.get(n - 1).getWeight() > weight)
return fillPackage(weight, item, n - 1);
else {
int include_cost = item.get(n - 1).getCost() + fillPackage((weight - item.get(n - 1).getWeight()), item, n - 1);
int exclude_cost = fillPackage(weight, item, n - 1);
if(include_cost > exclude_cost) {
my_pack.add(item.get(n - 1));
return include_cost;
}
else {
return exclude_cost;
}
}
}
这my_pack …
java algorithm arraylist knapsack-problem dynamic-programming
我很难理解下面的代码.它用可用面额的硬币('硬币')计算赚钱金额('n')的方法数量
def change(n, coins_available, coins_so_far):
if sum(coins_so_far) == n:
yield coins_so_far
elif sum(coins_so_far) > n:
pass
elif coins_available == []:
pass
else:
for c in change(n, coins_available[:], coins_so_far+[coins_available[0]]):
yield c
for c in change(n, coins_available[1:], coins_so_far):
yield c
n = 15
coins = [1, 5, 10, 25]
solutions = [s for s in change(n, coins, [])]
for s in solutions:
print s
输出:
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, …我正在处理这个问题,这与改变硬币问题很相似.
我需要实现一个简单的计算器,它可以用当前数字x执行以下三个操作:乘以x乘以2,将x乘以3,或者将x加1.
目标给出正整数n,找到从数字1开始获得数字n所需的最小操作数.
我做了一个贪婪的方法,它显示不正确的结果
import sys
def optimal_sequence(n):
sequence = []
while n >= 1:
sequence.append(n)
if n % 3 == 0:
n = n // 3
elif n % 2 == 0:
n = n // 2
else:
n = n - 1
return reversed(sequence)
input = sys.stdin.read()
n = int(input)
sequence = list(optimal_sequence(n))
print(len(sequence) - 1)
for x in sequence:
print(x)
例如:
Input: 10
Output:
4
1 2 4 5 10
4个步骤.但正确的是3个步骤:
Output:
3
1 3 9 10 …我有一个像这样的字符串:
$str = "eat.fruit.apple.good";
我要像这样使用这个数组:
$arr["eat"]["fruit"]["apple"]["good"] = true;
但我不明白如何动态创建它.谢谢戴维德
我们给出方数矩阵,例如
1 9 2
3 8 3
2 1 1
相邻数字之间的距离是2.我们希望在同一行或同一列中找到这样的两个数字,它们的总和加上它们之间的距离是最大的.例如,在上面的示例中,这些数字是9和8,并且最大结果是9+8+1*2 = 19.我们想要找到最大的结果,我们不需要具体的数字.
对我来说这看起来像是一个DP问题,但我想不出任何优雅的解决方案.
我正在尝试用给定条件编写背包c#算法,但我遇到的问题总是存在两个问题.我得到"索引超出了数组的范围"错误或我的结果只是0.
我找到了几个Knapsack实现的代码示例,但是我无法弄清楚我做错了什么.
代码示例:https: //www.programmingalgorithms.com/algorithm/knapsack-problem
http://www.csharpstar.com/csharp-knapsack-problem/
我的代码:
static int Knapsack(int n, int w, int[] s, int[] v)
{
int[,] G = new int[n+1,w+1];
for (int k = 0; k <= n; k++)
{
for (int r = 0; r < w; r++)
{
if (r == 0 || k == 0)
G[k, r] = 0;
else if (s[k] <= r)
G[k, r] = Math.Max(G[k- 1, r], v[k] + G[k - 1, r - s[k]]);
else
G[k, r] = G[k …问题陈述：
给定一个数组，任务是将其分为两组S1和S2，以使它们的和之间的绝对差最小。
采样输入，
[1,6,5,11]=> 1。2个子集为{1,5,6}和{11}，总和为12和11。因此答案是1。
[36,7,46,40]=> 23。2个子集为{7,46}和{36,40}，总和为53和76。因此答案是23。
约束条件
1 <=数组大小<= 50
1 <= a [i] <= 50
我的努力：
int someFunction(int n, int *arr) {
qsort(arr, n, sizeof(int), compare);// sorted it for simplicity
int i, j;
int dp[55][3000]; // sum of the array won't go beyond 3000 and size of array is less than or equal …