0

如果我输入数字：

3 10
7 6
5 5 
4 5

输出是：9。好的——这是正确的值。但如果我输入：

10 25
3 5
3 5
3 5 
3 5
3 5
3 5
3 5
3 5
3 5
3 5

正确的输出应该是：15 但我收到 2005985278。这段代码有什么问题？

#include<stdio.h>
#include<stdlib.h>
#define MA 29
int max(int a, int b) { 
return (a > b)? a : b; 
}
int knapsack(int W, int P[], int V[], int N)
{
int i, w;
int K[N+1][W+1];


for (i = 0; i <= N; i++)
  {
  for (w = 1; w <= W; w++)
    {
      if (i==0 || w==0)
          K[i][w] = 0;
      else if (P[i-1] <= w)
          K[i][w] = max(V[i-1] + K[i-1][w-P[i-1]],  K[i-1][w]);
      else
          K[i][w] = K[i-1][w];
    }
  }

return K[N][W];
}

int main()
{
int N,W,i;// N: Quantidade de Objetos - W: Capacidade da Mochila; i: interação
int Val=1;//V: Valor;
int Pes=1;//P: Peso;
do{

    scanf("%d %d",&N,&W);//ler N e W
    for (i=1;i<=N;i++) // iteração 
    scanf("%d %d",&Val,&Pes);//ler V
    //ler P
    int V[]={Val};//declaração do vetor V e recebendo Val do scanf
    int P[]={Pes};//declaração do vetor P e recebendo Pes do scanf
    printf("%d",knapsack(W, P, V, N));
    printf("\n");
    }while(N!=0 && W!=0);

return 0;
}

我需要输入物品数量N和容量W：

当我输入 N = 1, W - 7 和对象 P = 4, V = 5 时，输出为 4。

如果我输入其他值，例如 N = 10、W = 25 和 P = 3 3 3 3 3 3 3 3 3 3、V = 5 5 5 5 5 5 5 5 5 5，我会收到 2005985278 而不是 15。

请问我的代码有什么错误？

现在我的代码是这样的，但我在输出中收到错误：3 10 7 6 5 5 4 5

1 7 4 5

正确的输出是：9 和 4，我收到 7 和 0；在这种情况下，我如何在输入 N==0 && W==0 时添加程序的结尾？

#include<stdio.h>
#include<stdlib.h>
#define MA 29
int max(int a, int b) { 
return (a > b)? a : b; 
}
int knapsack(int W, int P[], int V[], int N)
{
int i, w;//interação;
int K[N+1][W+1];//declaração de K recebendo o valor de N e W +1;


 for (i = 0; i <=N; i++) // para i=0 i< = N incrementa i;
 {
   for (w = 0; w <= W; w++)
   {

       if (i==0 || w==0)
           K[i][w] = 0;
       else if (P[i-1] <= w)
             K[i][w] = max(V[i-1] + K[i-1][w-P[i-1]],  K[i-1][w]);
       else
             K[i][w] = K[i-1][w];
   }
 }

  return K[N][W];
 }

 int main()
{
 int N,W,i;// N: Quantidade de Objetos - W: Capacidade da Mochila; i: interação
 //P: Peso;


    while (scanf("%d %d", &N, &W) == 2)

{
    int V[N];
    int P[N];

for (i = 1; i <= N; i++)
    if (scanf("%d %d", &V[i], &P[i]) != 2)
        break;       
printf("%d\n", knapsack(W, P, V, N));
}

    }
4

1 回答 1

0

您的问题是您正在分配大小为 1 的数组，然后尝试访问这些数组中的 10 个元素。C 不会阻止你尝试，但它通常会给你错误的答案。

现有代码：

do{
    scanf("%d %d",&N,&W);   // Should test for success and terminate loop on failure
    for (i=1;i<=N;i++)
        scanf("%d %d",&Val,&Pes);  // Should check for success; should store values

    int V[]={Val};  // V is an array with one entry, the last value entered as Val.
    int P[]={Pes};  // P is an array with one entry, the last value entered as Pes.
    printf("%d",knapsack(W, P, V, N));
    printf("\n");
} while (N!=0 && W!=0);

C99 代码：

while (scanf("%d %d", &N, &W) == 2)
{
    int V[N];
    int P[N];
    for (i = 1; i <= N; i++)
        if (scanf("%d %d", &V[i], &P[i]) != 2)
            break;       
    printf("%d\n", knapsack(W, P, V, N));
}

请注意，如果您将输入打印到knapsack()函数中，无论是在调用代码中还是在函数本身中，您都会很快发现问题。在您完成阅读后打印输入数据是一种强大的技术。请注意，在您阅读时打印它可以掩盖在您完成阅读后打印会发现的问题。

显然，如果你的背包算法不正确，你仍然会得到错误的答案；我没有对此进行审查，也没有特别计划这样做。但是，您应该获得正确的输入数据，这极大地提高了获得正确输出的机会。

于 2013-04-14T02:38:00.040 回答