时间戳

首页 > 解决方案 > 背包实现未正确填充。已经尝试调试好几天了。还在学习

c++ - 背包实现未正确填充。已经尝试调试好几天了。还在学习

问题描述

代码执行 的可视化当我将它加载到可视化器中时，我的表格没有正确填充这个背包问题变化的最小值到底是什么问题？我意识到这似乎是一个懒惰的问题，但我已经花了好几天的时间，不知道出了什么问题。我还在学习。

#include<iostream> 
using namespace std;
void Minwater(int w[],int p[],int T,int n)/// Assumes n is last element of w[]
{
    int R[4][7];//Initialize array of n+1 row and T+1 cols
    for(int i = 0; i <= n+1; i++)
    {
        for(int j = 0; j <= T+1; j++)
        {
            if (i == 0 || j == 0)
                R[i][j] = 0;
            else if (w[i - 1] <= j)
                R[i][j] = min(p[i - 1] + R[i - 1][j - w[i - 1]],R[i - 1][j]);
            else
                R[i][i] = R[i - 1][j];
       
        }
      cout<< R[n][T];
    }
  
}

int main() {
  int w[3]={1,2,3};
  int T=6;
  int p[3]={10,15,40};
  Minwater(w,p,T,4);
  return 0;
}

该表假设取两个值中的最小值 min(p[i - 1] + R[i - 1][j - w[i - 1]],R[i - 1][j]) 但我似乎用全零填充它，并且整个表最终都不会填充。

标签： c++dynamicknapsack-problem

解决方案

首先，我认为我们不应该访问i - 1何时i == 0会导致不需要的行为，所以最好设置R[i][j] = 0 when i == 0

我也改为 max 因为如果你想使用 min 你应该将所有值设置为无穷大，否则 0 将是整个网格中的默认值

还要确保您的网格 R 未初始化为某个值，以便最大操作可以是决定性的（我添加 = {0}只是为了表明我们希望所有都等于零，您可能需要一个 for 循环来初始化所有它）

#include<iostream> 
using namespace std;
void Minwater(int w[],int p[],int T,int n)/// Assumes n is last element of w[]
{
    int R[4][7] = {0};//Initialize array of n+1 row and T+1 cols
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= T; j++)
        {
            if (i == 0)
                R[i][j] = 0;
            else if (w[i - 1] <= j)
                R[i][j] = max(p[i - 1] + R[i - 1][j - w[i - 1]],R[i - 1][j]);
            else
                R[i][i] = R[i - 1][j];
       
        }
      cout<< R[n][T];
    }
  
}

int main() {
  int w[3]={1,2,3};
  int T=6;
  int p[3]={10,15,40};
  Minwater(w,p,T,4);
  return 0;
}

推荐阅读