我正在尝试解决具有两个约束的背包问题。
我们所知道的：
- 列表项 项总数
- 列表项权重
- 列表项值
- 列表项 如果项目是否易碎(真/假(
约束：
- 列表项 背包的最大重量
- 列表项 背包可以容纳的易碎物品的最大数量。
谁能给我一些关于我应该使用的算法、伪代码或好文章的建议？
更新：
我忘了提的重要一点是，我还需要知道我把哪些物品放进了袋子里。
看起来对背包的修改可以解决这个问题。
假设我们有 N 个物品，最大 knapscak 重量为 W，最大易碎物品数量为 F
让我们将 dp 表定义为三维数组 dp[N
+1][W+1][F+1]现在 dp[n][w][f] 存储了如果我们用第一个项目子集填充背包可以获得的最大值n 个项目，重量为 w 且易碎物品
。FRO DP[n][w][f] 我们可以移动到状态：
- dp[n+1][w][f] 如果我们跳过第 n+1 个项目
- dp[n+1][w + weight(n+1(][f + isFragile(n+1(] 如果我们取第 n+1 个项目
所以伪 CDDE：
dp[N+1][W+1][F+1] // memo table, initially filled with -1
int solve(n,w,f)
{
if(n > N)return 0;
if(dp[n][w][f] != -1) return dp[n][w][f];
dp[n][w][f] = solve(n+1,w,f); //skip item
if(w + weight(n) <= W && f + isFragile(n) <=F)
dp[n][w][f] = max(dp[n][w][f], value(n) + solve(n+1, w + weight(n), f + isFragile(n)));
return dp[n][w][f]
}
print(solve(1,0,0))
获取实际的子集也不难：
vector<int> getSolution(n,w,f)
{
int optimalValue = solve(n,w,f);
vector<int>answer; //just some dynamic array / arrayList
while(n <= N)
{
if(solve(n+1,w,f) == optimalValue)n++; //if after skipping item we can still get optimal answer we just skip it
else //otherwise we cant so current item must be taken
{
int new_w = w + weight(n);
int new_f = f + isFragile(n);
answer.push_back(n); //so we just save its index, and update all values
optimalValue -= value(n);
n++;
w = new_w;
f = new_f;
}
}
return answer;
}
非递归方法
# N: number of items, W: max weight of knapsack, F: max amount of fragile items
# if item doesn't fit, then skip
# if it fits, check if it's worth to take it
dp[N+1][W+1][F+1] # filled with zeros
benefit, weight, fragility = [] # arrays filled with respective item properties
for n in range(1, N + 1):
for w in range(1, W + 1):
for f in range(0, F + 1):
if weight[n-1] > w or fragility[n-1] > f:
dp[n][w][f] = dp[n-1][w][f]
else:
dp[n][w][f] = max(dp[n-1][w][f],
dp[n-1][w-weight[n-1]][f-fragility[n-1]] + benefit[n-1])
print(dp[N][W][F]) # prints optimal knapsack value
列出项目
knapsack = [] # indexes of picked items
n = N
w = W
f = F
while n > 0:
if dp[n][w][f] != dp[n-1][w][f]:
knapsack.append(n-1)
w -= weight[n-1]
f -= fragility[n-1]
n -= 1
print(knapsack) # prints item indexes