Description
一个旅行者有一个最多能装m公斤的背包,现有n件物品,它们的重量分别是w1,w2,w3,...,wn,它们的价值分别为c1,c2,c3,...,cn。若每种物品只有一件,求旅行者能获得的最大总价值。
Input
m,和n(m<=200, n<=30)
接下来共n行每行两个整数wi,ci
Output
最大总价值
Sample Input
10 4
2 1
3 3
4 5
7 9
Sample Output
12
#include<stdio.h>
int Max(int x, int y)
{
if (x>y)
{
return x;
}
else
{
return y;
}
}
int d[31][201];
int main()
{
int m, n;
scanf("%d %d", &m, &n);
int w[31] = { 0 }, c[31] = { 0 };
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &w[i],&c[i]);
}
for (int i = 0; i <= m; i++)
{
d[0][i] = 0;
}
int max = 0;
for (int i = 1; i <= n; i++)
{
int j;
for ( j = 1; j <= m; j++)
{
if (j>=w[i])
{
d[i][j] = Max(d[i - 1][j], d[i - 1][j - w[i]] + c[i]);
}
else
{
d[i][j] = d[i - 1][j];
}
}
max = d[i][j];
}
printf("%d\n", max);
return 0;
}
你这程序流程本身就是有问题的吧!d数组中什么也没有,也没有进行赋值,这样的话当然会输出0