背包执行未正确填充.已经尝试调试好几天了.还在学习

Question

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

#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](但我似乎用全零填满了它，整个表格并没有填满。

Answer 1

首先，我认为我们不应该在i == 0时访问i - 1，这会导致不必要的行为，所以最好设置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;
}