hdu 2602 Bone Collector

典型的01背包问题，第一个代码是正确的，第二代码错了，一直不明白错在哪儿了？求高手指点！

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
	Copyright (c) 2011 panyanyany All rights reserved.

	URL   : http://acm.hdu.edu.cn/showproblem.php?pid=2602
	Name  : Bone Collector

	Date  : Friday，May 6，2011
	Time Stage : 1 hours around

	Result:
00665146	2011-05-06 01:44:42	Accepted	1001
31 MS	288 KB	Visual C++
pyy


Test Data:

Review:
//----------------------------------------------------------------------------*/
#include <iostream>
#include <string.h>
using namespace std;
const int size = 1010;
int tcase, bone, bag;
int value[size], weight[size], dp[size];

int knapsack()
{
	int i, j, k;
	memset( dp, 0, sizeof(dp) );
	for( i = 1; i <= bone; ++i )
	{
		for( j = bag; j >= weight[i]; --j )
			dp[j] = max( dp[j], dp[j-weight[i]] + value[i] );
	}
	
	return dp[bag];
}

int main()
{
	int i, j, k;
	while( cin >> tcase )
	{
		while( tcase-- )
		{
			cin >> bone >> bag;
			for( i = 1; i <= bone; ++i )
				cin >> value[i];
			for( i = 1; i <= bone; ++i )	
				cin >> weight[i];
			
			cout << knapsack() << endl;
		}
	}
	
	return 0;
}

错误代码

00665140

2011-05-06 01:20:21

Wrong Answer

1001

46 MS

4276 KB

Visual C++

pyy

#include <iostream>
#include <string.h>
using namespace std;
const int size = 1010;
int tcase, bone, bag;
int value[size], weight[size], dp[size][size];

void knapsack()
{
    int i, j, k;
    memset( dp, 0, sizeof(dp) );
    for( i = 1; i <= bone; ++i )
    {
        for( j = weight[i]; j <= bag; ++j )
            dp[i][j] = max( dp[i-1][j], dp[i-1][j-weight[i]] + value[i] );
    }
}

int main()
{
    int i, j, k;
    while( cin >> tcase )
    {
        while( tcase-- )
        {
            cin >> bone >> bag;
            for( i = 1; i <= bone; ++i )
                cin >> value[i];
            for( i = 1; i <= bone; ++i )    
                cin >> weight[i];
            knapsack();
            cout << dp[bone][bag] << endl;
        }
    }
    
    return 0;
}