数字を入力すると:
3 10
7 6
5 5
4 5
出力は : 9 です。OK — これが正しい値です。しかし、私が入力した場合:
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、V = 5 5 5 5 5 5 5 5 5 などの他の値を入力すると、15 ではなく 2005985278 が表示されます。
私のコードのエラーは何ですか?
私のコードはこれですが、出力にエラーが表示されます: 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));
}
}