- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我需要以递归、内存和动态编程的方式解决背包问题。目前我陷入了内存方法(以及部分动态编程方法)。
我根据在互联网上其他地方找到的代码改编了代码。目前输出不正确。
问题涉及利润和质量。每个商品都与利润和质量相关,可用商品数量为 MAX_N(数量),质量为 MAX_CAPACITY。目的是让背包里有尽可能多的“利润”。
以下是练习中提供的示例:
Example: Given a knapsack of capacity 5, and items with mass[] = {2, 4, 3, 2} and profit profit[] = {45, 40, 25, 15}, the best combination would be item 0 (with mass 2 and profit 45) and item 2 (with mass 3 and with profit 25) for a total profit of 70. No other combination with mass 5 or less has a greater profit.
完整代码如下:
#include <stdio.h>
#define MAX_N 10
#define MAX_CAPACITY 165
int m[MAX_N+1][MAX_CAPACITY+1];
int max(int x, int y) {
return x ^ ((x ^ y) & -(x < y));
}
int min(int x, int y) {
return y ^ ((x ^ y) & -(x < y));
}
int knapsackRecursive(int capacity, int mass[], int profit[], int n) {
if (n < 0)
return 0;
if (mass[n] > capacity)
return knapsackRecursive(capacity, mass, profit, n-1);
else
return max(knapsackRecursive(capacity, mass, profit, n-1), knapsackRecursive(capacity - mass[n], mass, profit, n-1) + profit[n]);
}
int knapsackMemoized(int capacity, int mass[], int profit[], int n) {
int take = 0;
int dontTake = 0;
if (m[n][capacity] != 0)
return m[n][capacity];
if (n == 0) {
if (mass[0] <= capacity) {
m[n][capacity] = profit[0];
return profit[0];
}
else {
m[n][capacity] = 0;
return 0;
}
}
if (mass[n] <= capacity)
take = profit[n] + knapsackMemoized(capacity-mass[n], mass, profit, n-1);
dontTake = knapsackMemoized(capacity, mass, profit, n-1);
m[n][capacity] = max(take, dontTake);
return m[n][capacity];
}
int knapsackDynamic(int capacity, int mass[], int profit[], int n) {
// this only works with int m[MAX_N+1][MAX_CAPACITY+1];
int i;
int j;
for (i = 0; i <= n; i++) {
for (j = 0; j <= capacity; j++) {
if (i == 0 || j == 0)
m[i][j] = 0;
else if (mass[i-1] <= j)
m[i][j] = max(profit[i-1] + m[i-1][j-mass[i-1]], m[i-1][j]);
else
m[i][j] = m[i-1][j];
}
}
return m[n][capacity];
}
void test() {
// test values
//int M1[MAX_N] = {2, 4, 3, 2};
//int P1[MAX_N] = {45, 40, 25, 10};
int M1[MAX_N] = {6, 3, 2, 4};
int P1[MAX_N] = {50, 60, 40, 20};
int M2[MAX_N] = {23, 31, 29, 44, 53, 38, 63, 85, 89, 82};
int P2[MAX_N] = {92, 57, 49, 68, 60, 43, 67, 84, 87, 72};
// a)
printf("Recursion: %d\n",knapsackRecursive(MAX_CAPACITY, M1, P1, MAX_N));
printf("Recursion: %d\n",knapsackRecursive(MAX_CAPACITY, M2, P2, MAX_N));
printf("\n");
// b)
printf("Memoization: %d\n",knapsackMemoized(MAX_CAPACITY, M1, P1, MAX_N));
printf("Memoization: %d\n",knapsackMemoized(MAX_CAPACITY, M2, P2, MAX_N));
printf("\n");
// c)
printf("Dynamic Programming: %d\n",knapsackDynamic(MAX_CAPACITY, M1, P1, MAX_N));
printf("Dynamic Programming: %d\n",knapsackDynamic(MAX_CAPACITY, M2, P2, MAX_N));
}
int main() {
test();
}
这是输出:
Recursion: 170
Recursion: 309
Memoization: 170
Memoization: 170
Dynamic Programming: 170
Dynamic Programming: 309
Process returned 25 (0x19) execution time : 0.014 s
Press any key to continue.
正如您所看到的,递归和动态编程解决方案提供了正确的输出。 (我通过函数运行给定的示例数组进行了检查。)内存方法目前没有。事实上,它总是为两个数组提供相同的结果,老实说我对此感到非常困惑。
另一个问题(尽管远没有那么大)是动态规划方法仅适用于 int m[MAX_N+1][MAX_CAPACITY+1];
但练习需要 int m[MAX_N][MAX_CAPACITY];
。我不确定如何更改代码以支持后者。
最佳答案
所以我知道这是一个家庭作业问题,所以我不会给出正确答案,但我可以这样说:
如果函数第二次运行时返回相同的答案,通常是因为某些内容尚未归零。上次运行留下了一些污垢。
检查所有您认为在函数范围之外创建的变量应该是干净的地方。
编辑:对于第二个问题,m[ITEM][CAP] 是一个矩阵,反射(reflect)每个项目剩余的每个上限的利润。这些项目是一个循环,对所有项目运行一次。 1 到 MAX
或 0 到 (MAX-1)
,这是一个具有 MAX 单元数的数组。每个项目的上限可以是从 0 到 MAX_CAP
的任意值(含)。该范围的长度为 MAX_CAP+1,这意味着您需要创建 int m[MAX_N][MAX_CAPACITY+1]
。我认为不可能以其他方式做到这一点,并且您的代码应该已经可以用于此目的。
关于c - 背包问题记忆化输出错误的解决方案,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30150519/
我正在使用 OUTFILE 命令,但由于权限问题和安全风险,我想将 shell 的输出转储到文件中,但出现了一些错误。我试过的 #This is a simple shell to connect t
我刚刚开始学习 Java,我想克服在尝试为这个“问题”创建 Java 程序时出现的障碍。这是我必须创建一个程序来解决的问题: Tandy 喜欢分发糖果,但只有 n 颗糖果。对于她给第 i 个糖果的人,
你好,我想知道我是否可以得到一些帮助来解决我在 C++ 中打印出 vector 内容的问题 我试图以特定顺序在一个或两个函数调用中输出一个类的所有变量。但是我在遍历 vector 时收到一个奇怪的错误
我正在将 intellij (2019.1.1) 用于 java gradle (5.4.1) 项目,并使用 lombok (1.18.6) 来自动生成代码。 Intellij 将生成的源放在 out
编辑:在与 guest271314 交流后,我意识到问题的措辞(在我的问题正文中)可能具有误导性。我保留了旧版本并更好地改写了新版本 背景: 从远程服务器获取 JSON 时,响应 header 包含一
我的问题可能有点令人困惑。我遇到的问题是我正在使用来自 Java 的 StoredProcedureCall 调用过程,例如: StoredProcedureCall call = new Store
在我使用的一些IDL中,我注意到在方法中标记返回值有2个约定-[in, out]和[out, retval]。 当存在多个返回值时,似乎使用了[in, out],例如: HRESULT MyMetho
当我查看 gar -h 的帮助输出时,它告诉我: [...] gar: supported targets: elf64-x86-64 elf32-i386 a.out-i386-linux [...
我想循环遍历一个列表,并以 HTML 格式打印其中的一部分,以代码格式打印其中的一部分。所以更准确地说:我想产生与这相同的输出 1 is a great number 2 is a great
我有下面的tekton管道,并尝试在Google Cloud上运行。集群角色绑定。集群角色。该服务帐户具有以下权限。。例外。不确定需要为服务帐户设置什么权限。
当尝试从 make 过滤非常长的输出以获取特定警告或错误消息时,第一个想法是这样的: $ make | grep -i 'warning: someone set up us the bomb' 然而
我正在创建一个抽象工具类,该类对另一组外部类(不受我控制)进行操作。外部类在某些接口(interface)点概念上相似,但访问它们相似属性的语法不同。它们还具有不同的语法来应用工具操作的结果。我创建了
这个问题已经有答案了: What do numbers starting with 0 mean in python? (9 个回答) 已关闭 7 年前。 在我的代码中使用按位与运算符 (&) 时,我
我写了这段代码来解析输入文件中的行输入格式:电影 ID 可以有多个条目,所以我们应该计算平均值输出:**没有重复(这是问题所在) import re f = open("ratings2.txt",
我需要处理超过 1000 万个光谱数据集。数据结构如下:大约有 1000 个 .fits(.fits 是某种数据存储格式)文件,每个文件包含大约 600-1000 个光谱,其中每个光谱中有大约 450
我编写了一个简单的 C 程序,它读取一个文件并生成一个包含每个单词及其出现频率的表格。 该程序有效,我已经能够在 Linux 上运行的终端中获得显示的输出,但是,我不确定如何获得生成的显示以生成包含词
很难说出这里要问什么。这个问题模棱两可、含糊不清、不完整、过于宽泛或夸夸其谈,无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开,visit the help center . 关闭 1
1.普通的输出: print(str)#str是任意一个字符串,数字··· 2.格式化输出: ?
我无法让 logstash 正常工作。 Basic logstash Example作品。但后来我与 Advanced Pipeline Example 作斗争.也许这也可能是 Elasticsear
这是我想要做的: 我想让用户给我的程序一些声音数据(通过麦克风输入),然后保持 250 毫秒,然后通过扬声器输出。 我已经使用 Java Sound API 做到了这一点。问题是它有点慢。从发出声音到
我是一名优秀的程序员,十分优秀!