HDU 2602 Bone Collector（dp之01背包问题）
题目描述：
典型的01背包问题。
#include <iostream>
#include <cstdio>
#include <cstring>
#define N 1010
using namespace std;
int dp[N][N];
int temp;
int value[N] ;
int volume[N];
int T;
int number , volumeSum ;
void init()
{
memset( value, 0 , sizeof(value) );
memset( volume, 0 , sizeof(volume) );
memset( dp, 0 , sizeof(dp) );
}
void input()
{
cin >> number >> volumeSum;
for ( int i = 1 ; i <= number ; i++ )
scanf("%d", &value[i]);
for ( int i = 1 ; i <= number ; i++ )
scanf("%d", &volume[i]);
}
int knapsack( int number ,int volumeSum)
{
for( int i = 1 ; i <= number ; i++ )
for( int j = 0 ; j <= volumeSum ; j++ )
{
if (volume[i] > j)
{
dp[i][j] = dp[i-1][j];
continue;
}
else if ( dp[i-1][j-volume[i]] + value[i] > dp[i-1][j])
{
dp[i][j]=dp[i-1][j-volume[i]]+value[i];
continue;
}
else
dp [i][j] = dp [i-1][j];
}
return dp[number][volumeSum];
}
int main()
{
cin >> T;
while ( T-- )
{
init();
input();
cout << knapsack( number , volumeSum ) << endl;
}
return 0;
}