改进的0-1背包
问题是动态规划中的经典问题，它是经典0-1背包问题的一种改进版本。在改进的0-1背包问题中，我们需要在给定的一组物品中选择若干个物品放入背包，使得放入背包的物品总重量不超过背包的承重限制，同时使得放入背包的物品总价值最大化。
不同于经典0-1背包问题，改进的0-1背包问题中每个物品的重量和价值可以是小数，而不仅仅是整数。这意味着我们可以选择将物品的一部分放入背包，而不是必须要整个物品放入或不放入背包。同时，在改进的0-1背包问题中，每个物品的重量和价值可能不同，我们需要根据物品的重量和价值进行权衡，找到最佳的组合。
改进的0-1背包问题可以通过动态规划算法来解决。我们可以使用一个二维数组dp来记录每个状态的最大价值，其中dp[i][j]表示前i个物品放入重量不超过j的背包中的最大总价值。状态转移方程可以表示为：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
其中，w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。根据状态转移方程，我们可以从前往后遍历物品，依次计算dp数组的值，最终得到dp[n][W]，其中n表示物品的个数，W表示背包的承重限制。
改进的0-1背包问题在实际应用中有很多场景。例如，在资源调度中，我们可以将资源看作物品，将资源的容量看作背包的承重限制，通过求解改进的0-1背包问题来实现资源的最优分配。在网络流量控制中，我们可以将网络中的各个节点看作物品，将网络的总容量看作背包的承重限制，通过求解改进的0-1背包问题来实现流量的最优分配。
推荐的腾讯云相关产品和产品介绍链接地址：
- 云服务器（CVM）：提供灵活可扩展的云服务器，满足不同规模的应用需求。
- 对象存储（COS）：提供安全可靠的大规模对象存储服务，支持海量数据的存储和访问。
- 云数据库 MySQL 版（TencentDB for MySQL）：提供稳定可靠的云数据库服务，支持高性能的 MySQL 数据库引擎。
- 腾讯云函数（SCF）：无服务器的事件驱动型计算服务，帮助开发者实现按需计算和自动扩缩容。
- 人工智能平台（AI Lab）：提供丰富的人工智能开发工具和服务，支持图像识别、语音识别、自然语言处理等多种 AI 应用场景。
这些腾讯云的产品可以帮助您在云计算领域进行开发和部署，实现高效、稳定、安全的解决方案。
相关·内容
我看到一维数组是在无界背包情况下构造的，而二维数组是在0/1背包情况下构造的？这一切为什么要发生？这个问题是关于动态规划的。
浏览 2提问于2019-12-30得票数 4
回答已采纳
2回答
我有一个背包问题，有指定的背包重量和重量计数能力。
我需要一种算法，当背包容量为C，所需权重计数为N，并且有一个权重列表时，将权重打包到背包。权数的排序并不重要。如果算法是递归的，这将是最好的。
例如：
我有背包巫婆只能装3个重量，他们必须有10个重量，我有这些重量: 9，8，7，2，1。正确的答案是7，2，1。
最好是有人写伪代码，但如果它是任何一种常见的编程语言，那就好了。
P.S.任何值得赞赏的提示:)
编辑需要给出答案的算法，精确的N个权重计数，其中的权重精确C。
浏览 4提问于2011-03-27得票数 1
1回答
最小零钱或0-1背包
、、、
我有这样的数据集：
长度: 233,333,450,560,650,780限制: 5400
现在我的问题是从设置的最高到最低的长度中选择项目，以弥补限制或尽可能接近。
我知道背包和最小零钱都能解决我的问题。我想知道哪一个更好。
请注意，硬币兑换使用贪婪算法，背包使用动态编程
浏览 4提问于2019-07-26得票数 0
2回答
双权值背包算法
、、、、
我有以下问题：
假设每个对象都有权重w1或w2 (只有两个权重)，则解决背包0-1问题(而不是小数)。Capacity=W，算法必须在O(nlogn)上运行。
我试图求解，贪婪算法不起作用，动态规划算法是O(n*W)。
有人能给我个提示吗。谢谢。
浏览 0提问于2016-07-03得票数 4
回答已采纳
在Geeks的上，我们提到“如果输入值很高，那么0-1背包的解就不可行，并且需要近似解。”
而在近似解，即FPTAS解中，与权值对应的值是这样修改的：
K= (maxVal *ε) /n
val'i =楼层(vali/ k)
然后应用相同的基于DP的解决方案。
我的怀疑是，实际的基于DP的0-1背包解决方案的复杂性取决于背包和No的重量。关于物品的。它不涉及值，那么为什么如果值很高，那么我们需要近似解？这样做会使近似解的复杂性比实际解更好吗？
浏览 0提问于2019-01-09得票数 0
据我所知，在一个0-1背包问题中，只允许同一个变体的0或1个对象。不如把每个重量除以它的值，得到相应的比例，然后把每一个比率从最大的开始，放到背包里，直到达到允许的最大重量？它的时间复杂度不是比动态规划解决方案好吗？
浏览 3提问于2017-04-18得票数 0
回答已采纳
1回答
具有两个约束的0-1背包动态规划
、、、、
对于具有给定n项的权重和值的0-1背包问题，以及最大权重容量W，我知道可以使用动态方法用双嵌套循环来求解。
我的问题是，如果我们说每个n项都有一个额外的“卷”值和一个最大容量V，那么如何更改算法呢？该算法会成为一个具有时间复杂度O(n*W*V)的三重嵌套循环吗？
浏览 10提问于2021-12-08得票数 2
1回答
我有以下问题，我想解决与excel求解器或任何其他工具(任何建议是欢迎的)，但我不想写代码。
我有几件东西(大约40件)要放在几个背包里(大约5件)。每件东西都有不同的重量，但每个背包都有相同的空间。
这些物品的重量之和远远小于背包的容量。
我需要做的是分配背包中的物品，用或多或少相同的重量填充它们。换句话说，减少方差。
有一个限制:有些项目不能放在一起。我有一个列表(或邻接矩阵)，列出了可以或不能放在一起的项目。
当然，一旦一件物品放在背包里，就不能再放第二件了(每件物品中只有一件)。
我试图用excel求解器解决这个问题，但所有3个算法都说它们找不到解决方案，但我可以手动找到它们，所以我认
浏览 8提问于2016-09-19得票数 1
回答已采纳
1回答
我对01背包问题很熟悉，因为它的目标是将符合重量约束的物品放在背包中。最大背包和MinCost背包有什么区别？在哪一个给我一个预算或目标值？
浏览 1提问于2017-04-27得票数 0
回答已采纳
1回答
我在互联网上读过两个截然不同的问题0-1背包问题和无界背包问题。我发现，这两个问题都是通过动态规划解决的，但方法不同。如果用二维数组求解0-1背包问题，则无界背包问题仅使用一维数组。
您可以阅读更多的和。
正如我所知，这两个问题的不同之处在于，0-1背包问题只包含有限的东西，而无界背包问题允许获取任何资源的一个或多个实例。不过，我不知道为何要改变解决这个问题的方法呢？你能告诉我原因吗？
浏览 3提问于2020-07-23得票数 1
回答已采纳
在我的代码中，假设C是容量，N是物品数量，wj是物品j的权重，vj是物品j的值，它会做与0-1背包算法相同的事情吗？我已经在一些数据集上尝试了我的代码，情况似乎就是这样。我想知道这是因为我们学到的0-1背包算法是2维的，而这是1维的：
for (int j = 0; j < N; j++) {
if (C-w[j] < 0) continue;
for (int i = C-w[j]; i >= 0; --i) { //loop backwards to prevent double counting
dp[i + w[j]] = max(dp
浏览 2提问于2011-12-31得票数 7
回答已采纳
1回答
几天前，我读到关于分数背包问题的贪婪算法和动态规划的文章，我发现这个问题可以用贪婪的方法来最优地解决。有人能给出一个用动态规划方法来解决这个问题的例子或解决方案吗？
我知道贪婪的方法是解决这个问题的最好方法，但我想知道动态规划是如何解决这个问题的。
浏览 2提问于2020-06-04得票数 1
1回答
问题陈述：给出n个大小为Ai的项目，整数m表示背包的大小。这个背包你能装满多少？
示例1:输入: 3,4,8,5，背包size=10输出:9
例2:输入: 2,3,5,7，背包size=12输出: 12
我必须用回忆录写解决方案，我知道自下而上的dp会很快，但你能帮我其他优化，我可以添加到这个解决方案。
class Solution {
public:
unordered_map<string,int>m1;
int solve(int m,vector<int>&a,int i){
if(i<0)return 0;
浏览 2提问于2020-04-27得票数 1
1回答
以下是背包/背包问题的含义(摘自维基百科)：
给定一组项目，每一项具有一个权重和一个值，确定要包含在集合中的每个项目的数量，以便总权重小于或等于给定的限制，并且总价值尽可能大。它的名字来源于一个人所面临的问题，他被一个固定大小的背包所束缚，必须用最有价值的物品来填充它。
关于- https://en.wikipedia.org/wiki/Knapsack_问题 -这是0-1背包或0-1背包问题的定义：
📷
下面是我在python中的"0-1背包问题“的版本：
def knapsack(capacity, items, weights, values):
grid = [[0]
浏览 0提问于2019-05-18得票数 3
回答已采纳
2回答
我是一名研究人员。我正在搜索背包问题的大量数据。我想测试我的背包问题的算法。但我找不到大数据。我需要的数据有1000项和容量是无关紧要的。重点是项目一样庞大，这对我的算法是有好处的。互联网上有没有可用的海量数据？有没有人知道求求你们我需要急事。
浏览 1提问于2010-05-23得票数 7
1回答
当我阅读背包问题()的解决方案时，我不明白为什么参数中有迭代数n。似乎我们可以通过检查通过的限制来讨论叶用例。例如。15公斤的背包问题，解决办法似乎是：
Value(n, W){ // W = limit, n = # items still to choose from
if (n == 0) return 0;
if (arr[n][W] != unknown) return arr[n][W]; // <- add memoize
if (s[n] > W) result = Value(n-1,W);
else result = max{v[
浏览 2提问于2013-08-20得票数 2
回答已采纳
2回答
无法理解背包解决方案
、、、、
在wikipedia中，背包的算法如下：
for i from 1 to n do
for j from 0 to W do
if j >= w[i] then
T[i, j] := max(T[i-1, j], T[i-1, j-w[i]] + v[i]) [18]
else
T[i, j] := T[i-1, j]
end if
end for
end for
我在网上找到的所有例子都是相同的结构。
我无法理解的是，这段代码是如何考虑到这样一个事实:也许最大值来自一个较小的背包？例如，如果背包
浏览 7提问于2013-01-03得票数 1
1回答
如何计算找到这种松弛。我该知道什么才能找到它。假设我有n件物品和我的背包。所以我想知道m松弛的次数。至少有人能给我一些想法。我已经找了很久了。网上有一些文章，但不太清楚。请至少有人对我说，你应该读这东西，你应该知道这件事。
谢谢
浏览 0提问于2010-06-27得票数 0
2回答
我是数据结构和算法的新手，想知道贪婪方法和动态编程(DP)方法。经过长时间的努力，我似乎掌握了解决DP问题的一步一步的方法。然而，我似乎误解了需要贪婪地处理DP问题的问题。根据定义，贪婪方法意味着我们在每一步都选择最好的解决方案，而DP有重叠子问题。
我困惑的根源是，我首先递归地解决DP问题，然后寻找重叠的子问题，并使用memoisation来改进解决方案。
我的问题是，我是否可以将DP问题的递归解决方案称为贪婪的解决方案。例如，在解决流行的背包问题时，我们要么选择在背包中添加一个项目，要么选择不添加。然后，我们在每一步都选择可能的最佳结果。现在背包问题有重叠子问题，是DP问题。但我的问题是，
浏览 7提问于2021-01-01得票数 0
2回答
我有一个从0到3的5x5表，包括所有未知的值。我知道每个行和列的值和零数。我将如何使用C#解决这个0-1背包问题，并检索满足已知和数和零数的可能解？表总是五行五列，所以它不是一个传统的背包。
例如，假设我们输入：
Row[0]: Sum=4, Zeros=1
[1]: Sum=5, Zeros=1
[2]: Sum=4, Zeros=2
[3]: Sum=8, Zeros=0
[4]: Sum=3, Zeros=2
Col[0]: Sum=5, Zeros=1
[1]: Sum=3, Zeros=2
[2]: Sum=4, Zeros=2
[3]:
浏览 5提问于2011-09-04得票数 4
回答已采纳
1回答
这是在极客上为极客找到的0-1背包问题动态编程代码。我已经为我自己的测试更改了输入，但它似乎不起作用。最优解不是第4项(v:10，w:7)的1和第1项(v:1，w:1)的3加起来是13吗？当我运行代码并手动执行算法时，结果是包含第2项和第4项的结果是12。我哪里错了？
// A Dynamic Programming based solution for 0-1 Knapsack problem
#include<stdio.h>
// A utility function that returns maximum of two integers
int max(int a, i
浏览 0提问于2018-03-05得票数 2
2回答
我有一个使用动态编程解决背包问题的python代码。此函数返回最佳子集的总成本，但我希望它返回最佳子集的元素。有人能帮我吗？
def knapSack(W, wt, val, n):
K = [[0 for x in range(W + 1)] for x in range(n + 1)]
# Build table K[][] in bottom up manner
for i in range(n + 1):
for w in range(W + 1):
if i == 0 or w == 0:
浏览 3提问于2018-04-08得票数 0
我遇到了一个问题，目标是使用动态编程(而不是其他方法)。有一段距离要跨越，一组不同长度的电缆。准确地说，跨越距离所需的最小电缆数是多少？
在我看来，这看起来像一个背包问题，但是由于可能有一个特定长度的倍数，所以它是一个有界背包问题，而不是0/1背包问题。(将每一项的价值视为其重量。)采用朴素的方法(不考虑搜索空间的扩展)，将有界背包问题转化为0/1背包问题的方法，简单地将倍数分解为单数，并应用著名的动态规划算法。不幸的是，这导致了次优结果。
例如，给定电缆：
1x10英尺，
1x7英尺，
1x6英尺，
5x3英尺，
6x2英尺，
7x1英尺
如果目标跨度为13英尺，则DP算法选择7
浏览 0提问于2011-10-31得票数 12
回答已采纳
3回答
标准的0/1背包要求每个项目的重量独立于其他项目。然后，DP算法是解决该问题的有效算法。但是现在我遇到了一个类似的但扩展了这个问题的
新物品的重量取决于背包中已有的物品。
例如，，我们有5项-- a，b，c，d和e，有重量w_a，.，w_e。item b和c具有权重依赖性。
当b已经在背包中时，item c的权重将小于w_c，因为它可以与b共享一些空间，即weight(b&c) < w_b + w_c。对称地说，当c已经在背包中时，b的重量将小于w_b。
这种不确定性导致了原DP算法的失败，因为它依赖于以前迭代的正确性，而这些迭代现在可能不正确。我读过一些关于背包的论文，
浏览 4提问于2016-08-10得票数 33
回答已采纳
2回答
带重复的背包算法
、、、
我试图为背包算法设计一个伪代码，其中一个项目可以被多次选择。经典算法是
OPT(i, w) = max(OPT(i-1, w) or vi + OPT(i-1, w-wi))
为了满足要求，我将其修改为
k=1;
max = maximum(OPT(i-1, w))
while(OPT(i-1, w - k*wi) > 0) {
maximum = max(maximum, k*vi + OPT(i-1, w - k*wi))
k++
}
OPT(i, w) = maximum
这似乎是一个适当的解决办法吗？还是有更好的解决方案？如果需要更多的信息，请告诉我。Rest都保持不变，
浏览 4提问于2015-10-24得票数 4
回答已采纳
1回答
背包算法的一个变体
、、、
我有一个项目列表，a, b, c,...，每个项目都有一个权重和一个值。
“普通”背包算法将发现选择的项目，使所选项目的价值最大化，同时确保权重低于给定的约束。
我遇到的问题略有不同。我希望最小化该值(通过使用该值的倒数来简化)，同时确保权重至少为--至少--给定约束的值，不小于或等于该约束的值。
我尝试过通过普通的背包算法重新路由这个想法，但这是不可能的。我希望有另一个组合算法，我没有意识到，这样做。
浏览 0提问于2018-02-01得票数 1
1回答
学习课程
我已经实现了一个仅使用两行的0-1背包算法。
它输出正确的最终值。
Names包含正在使用的每个元素的id。
def KnapSack(val, wt, n, W):
names = n
n = len(n)
mat = [[0 for i in range(W + 1)] for i in range(2)]
i = 0
while i < n:
j = 0
if i % 2 == 0:
while j < W:
j += 1
浏览 1提问于2018-12-07得票数 4
1回答
对于那些不熟悉FPL的人，这里有一个简短的版本。无论是守门员、后卫、中场球员还是前锋，你都有球员。每个玩家都有一些价格(或者四舍五入到.5或者.0)，并且根据他们的真实生活表现你可以得到分数。你有一个100 on的预算，你需要建立一个团队，记住你有一个限制球员在每个位置。
现在的问题是:如果你有所有球员的价格，他们的位置和他们在一个赛季中得分的总数，你如何找到得分最高的球队，比如4-4-2阵型？(1 1GK，4 4DEF，4 4MID，2 2FWD)。
我想这是背包问题的一个变体，在这个问题上，你有足够的限制，只有11名球员，而且有4-4-2的阵型。那么，这是解决这个问题的最佳方法吗?如果有这
浏览 0提问于2018-07-15得票数 0
WordPress为用户提供了对翻译做出贡献的可能性，例如喷气背包。
这些翻译是自动下载到WordPress安装中，还是首先由插件所有者进行审批工作？
浏览 0提问于2016-11-23得票数 2
如果使用动态规划来获得某个问题的最优解。您如何重构导致该解决方案的实际步骤？
例如，在0-1背包问题中，使用递归
使用这一点，我们可以得到背包中可以出现的最大值。您如何找到实际存在的项目。
这是否可以推广到任何动态编程解决方案。例如。找出属于最长递增子序列的实际nos，其解已使用动态规划获得。
浏览 0提问于2011-10-19得票数 2
回答已采纳
1回答
最近我用python编写了一个解决背包问题的程序。它工作得很好，通常遵循贪婪的算法(即为每一步找出最佳的解决方案，直到它结束)
但是我需要基于贪婪的算法(这是我的作业的一部分)对优化它。
那么，你能给我一些基本的想法来改进它吗？
Item Name Weight Profit
Ammunition 3.00 95.00
Bread 3.60 90.00
Firewood 2.50
浏览 1提问于2012-03-14得票数 0
回答已采纳
在背包问题中，我们通常试图最大化背包中商品的价值，同时保持商品的总重量<= C，其中C是背包的容量。当货物的总重量应该恰好等于背包的容量= C时，我该如何解决这个问题？
浏览 0提问于2014-03-18得票数 0
在这个多背包问题的变体中，只考虑了项目的权重，所以我想它更像是一个多子集和问题，但是用背包更容易解释。
有一些n背包，每个背包都装满了各个项目，以其各自的最大重量容量C[j]，其中0 <= j < n。
背包被倒进一堆，总共有一个m项目，每个项目都有一个重量W[i]，其中有一个0 <= i < m。该桩中的项目被洗牌，k项目被从桩中移除，其中0 <= k <= m。
n、m、C[j]和W[i]是大于零的整数；i、j和k是非负整数.
此状态是包装算法的初始输入。
如何重新包装所有剩余的m - k项，从而不超过每个背包C[j]的单独容量？
封隔器不知道背包以
浏览 0提问于2019-02-18得票数 0
我在练习递归算法，因为虽然我喜欢递归，但当有“双重”递归进行时，我仍然会遇到麻烦。所以我创建了这个蛮力0-1背包算法，它将输出最终的权重和最佳值，它非常好，但我认为只有当你知道这些数字背后的项目时，信息才是相关的。不过，我被困在这里了。我想优雅地做到这一点，而不是创建一团糟的代码，也许我过度限制了我的想法，试图实现这个目标。我想我应该在这里发布代码，看看是否有人有一些关于添加代码来输出所选项目的好主意。这是Java：
public class Knapsack {
static int num_items = 4;
static int weights[] = { 3, 5, 1, 4 };
浏览 3提问于2017-04-24得票数 0
我正在编写一个采用背包问题形式的算法。我试图在给定最大重量(W)的情况下最大化背包的值(V)。陷阱是每个项目(I)只能选择一次，背包(无论重量)只能容纳10个项目，并且有非常多的项目(500+)。
到目前为止，我的想法是生成一个超重的背包，并递归地向后工作，一次替换一个项目，直到它达到最大重量<=。这对于生成最优的背包来说不是问题，然而，我真的很想生成以下100个左右的背包。我在想，我可以通过继续我的递归过程来做到这一点，然而，我并不觉得这是完全准确的，因为可能会缺少稍微更优的背包。
浏览 0提问于2016-12-30得票数 0
1回答
折叠背包问题是普通背包问题的推广，其中背包容量是包含的项目数量的非增函数。
有人知道什么吗(名字，文献，算法...)关于背包容量根据您选择的项目(即，域是项目的powerset )而不是项目数量而变化的变体？
浏览 2提问于2013-10-09得票数 1
0回答
在经典的基于动态规划的无界背包算法()中，我们分配一个背包大小的整数数组来存储最大值。
如果我有一个10亿大小的背包，我如何优化DP解决方案以确保我可以容纳int[] knapsack阵列？因为Java为1B大小的背包占用的内存=内存的10^9 * 4Bytes = 3.7GB。
浏览 5提问于2016-12-29得票数 0
3回答
填充两个背包的最佳方法？
、、、
在一个背包的情况下，最优填充背包的动态规划算法工作良好。但是，是否有一种有效的已知算法可以最优地填充2个背包(容量可能是不相等的)？
我试过以下两种方法，但这两种方法都不正确。
首先使用最初的DP算法填充第一个背包，然后填充另一个背包。
首先填充大小为W1 + W2的背包，然后将解决方案拆分为两个解决方案(其中W1和W2是两个背包的容量)。
问题陈述(参见维基百科的 )：
我们必须用一组物品填充背包(每个项目都有一个重量和一个值)，以便在总重量小于或等于背包大小的情况下，最大限度地利用这些物品的价值。
我们不能多次使用一个项目。
我们不能使用项目的一部分。我们不能拿
浏览 8提问于2013-02-09得票数 17
回答已采纳
1回答
我已经成功地用C++编写了算法，以获得整数背包、小数背包和混合类型背包的最优解，所有这些都有或没有限制每件物品允许携带的数量。 这些只处理具有单一约束的项目，这是权重。如果我想解决一个可能有2+约束的背包，我会从我已经编写的其他代码中提取出来，或者需要编写一个全新的算法吗？ 整数和混合类型的背包被写成求解动态规划，而小数类型的背包则使用贪婪。 例如。给定两个整数项和一个小数项。 各个值分别为(9，8，3) 各个权重为(2，3，1)最大权重=24 各卷的最大Volume=23为(3，2，2) 找到最优解并求和。 我想我已经计算出这个和是77.5
浏览 25提问于2020-06-24得票数 1
2回答
我有一个场景，我需要一些帮助来制定问题，这样我就可以正确地实现一个优化方法。我希望有人能给我一点指导，表面上看起来很简单，但是我很难找到正确编码变量、约束等的方法。
设想的情况是：
需要将多个物品放入垃圾箱/背包中。
每件物品都有两个在包装时必须考虑的因素。
我有几种可以用来包装的垃圾箱/背包
垃圾箱/背包的供应是无限的。
每个bin /背包对来自项的每个值都有约束，因此项的值以累积的方式加起来，但不能超过bin /背包上的任何一个约束。
每个垃圾箱/背包都有不同的使用成本(价格)。
可以装进垃圾箱/背包的物品的数量有一个上限，而不管里面有哪些物品。
示例：
浏览 1提问于2019-01-17得票数 0
1回答
无重量约束背包
、、、、
我刚刚遇到了以下问题(它使我想起背包问题，但有一些不同之处)：
你得到了许多物品，你必须把它放在背包里，并获得最大的利润。每个项目都有特定的利润价值和特定的形状。由于它们的形状，有些物品不能放在背包里。与一般的背包问题不同，没有最大重量限制背包中物品的数量。您还将为每个项目提供一个列表。在该列表中，您可以看到可以与相应项一起放入背包中的项目。
是否有计算最优解的算法？还是NP完全问题？在这种情况下，有没有近似的方法？
浏览 3提问于2016-02-09得票数 3
回答已采纳
有没有什么资源可以让我找到解决动态编程问题的真实代码，比如PHP中的背包问题等等？
我想自己分析代码，因为我不太理解理论。我在谷歌里找不到任何代码。
非常感谢。
浏览 1提问于2010-11-28得票数 5
回答已采纳
在我的项目中，我有学生和背包实体。Backpack引用学生(一对多)。所以我在数据库中有一个学生记录，它有两个背包。我正在从数据库加载学生，并获得背包计数。在这种情况下，它返回两个。当我将一个新的背包添加到列表中时，它将从集合中删除现有的两个背包。我不能发布我的代码，因为太复杂了。我试着解释一下我在做什么。在背包中的学生引用属性设置器中，我正在检查该背包是否存在于学生的背包集合中。如果不是，则将背包添加到列表中。然后我将该对象添加到实体框架上下文中。下面是实现该功能的代码：
if (entity != null && EFContext.Entry(entity
浏览 1提问于2017-05-03得票数 0
我正在为即将到来的测试复习一下，想知道是否有人可以重复一下问题的b部分。这是发出去的复习表中的文本，但我不确定b部分到底在问什么。我猜更严格地说，什么是“产生一个不到0/1背包问题最优解的1%的解”。
a)解决背包问题的以下实例，即，给出所选每个对象的分数和最优背包的值。显示步骤：
背包容量C= 100
**在这里他列出了对象、它们的值和权重。在表中**
b) 10pt给出了一个具有两个对象的示例，表明用于分数背包问题的相同贪婪方法(略有修改，如果不适合，则去掉贪婪方法选择的最后一个对象)产生的解小于0/1背包问题的最优解的1%。
浏览 1提问于2012-11-26得票数 0
1回答
这是一个古老而著名的背包问题：
这里我有一个约束的背包问题。
我有大小为W = 100000000和N = 100的背包，我为其编写了动态解决方案，我的算法的复杂性是O(100000000*100)，这在时间和空间上都太大了，但是这里有一个条件，即无论是W ≤ 50000 or max 1≤ i ≤ n Vi ≤ 500.还是W ≤ 50000 or max 1≤ i ≤ n Vi ≤ 500.，所以如果背包大小超过50000，则项目的最大值是有限的。
所以，现在我想知道，在这种情况下，如何降低算法的时间复杂度?我认为背包问题取决于背包的大小和项目的数量，那么项的值如何改变我的算法？
浏览 7提问于2015-06-23得票数 0
回答已采纳
1回答
我想知道是否有一些情况可以只使用其中之一来解决(即只能使用带重复的背包或不带重复的背包)，或者这两种情况是否总是可以相互简化。
为了澄清，我们给出了n个项目1...n，其中项目i具有权重w_i和值v_i，并且正在尝试选择项目的组合，使得在总权重保持在小于某个W的情况下使总值最大化。
没有重复的背包公式(就动态编程而言)是
K(w, j) = max{K(w-w_j, j-1) + v_j, K(w, j-1)}
其中K(w，j)是指使用容量为k的背包和项目1...j可达到的最大值，而具有重复的背包的公式为
K(w) = max{K(w-w_i) + v_i | w_i <= w}
其中K
浏览 1提问于2015-11-03得票数 0
1回答
这个问题是我在工作中实现某个系统时遇到的一个重新表述的问题。我认为这有点类似于背包问题，并好奇地探索如何解决它，因为我不能提出一个解决方案。 问题陈述:给定一组物品，每个物品都有重量和价值，以及两个背包，确定在这两个背包中包括哪些物品，使每个背包的重量恰好为K，并且这两个背包的价值总和的差值尽可能小。如果不可能满足两个背包的权重约束，则算法应该不返回任何内容。 我认为某种贪婪的算法可能是一个令人满意的解决方案，但不确定如何编写它。
浏览 18提问于2020-07-03得票数 0
回答已采纳
1回答
我有n件物品和m个背包。每件物品都有一个利润和重量，这取决于把物品放在哪个背包里。例如，对于项目1，背包m=1和2 respectively.Also的利润分别为9和10，背包m=1和2的重量分别为3 Kg和4 Kg。这个问题属于哪一类背包问题？有没有一个有效的方法来解决这个问题？
我真的很感谢你的帮助。
浏览 0提问于2015-08-19得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
