限制条件：

1<=N<=100

1<=wi 、vi<=100

1<=wi<=10000

样例：

输入

N=4

W[N] = {2, 1, 3, 2}

V[N] = {3, 2, 4, 2}

输出

W = 5(选择0，1，3号)

（2）解题分析：

   用普通的递归方法，对每个物品是否放入背包进行搜索

#include <stdio.h>
#include <tchar.h>
#include <queue>
#include "iostream"
 
using namespace std;
 
const int N = 4;
const int W = 5;
int weight[N] = {2, 1, 3, 2};
int value[N] = {3, 2, 4, 2};
int solve(int i, int residue) 
{
int result = 0;
if(i >= N)
return result;
if(weight[i] > residue)
result = solve(i+1, residue);
else 
{
result = max(solve(i+1, residue), solve(i+1, residue-weight[i]) + value[i]);
}
 
}
 
int main() {
int result = solve(0, W);
cout << result << endl;
return 0;
}

（2）解题分析：

   用记录结果再利用的动态规划的方法，上面用递归的方法有很多重复的计算，效率不高。我们可以记录每一次的计算结果，下次要用时再直接去取，以提高效率

#include <stdio.h>
#include <tchar.h>
#include <queue>
#include "iostream"

using namespace std;

const int N = 4;
const int W = 5;
int weight[N] = {2, 1, 3, 2};
int value[N] = {3, 2, 4, 2};
int record[N][W];
void init()
{
	for(int i = 0; i < N; i ++)
	{
		for(int j = 0; j < W; j ++) 
		{
			record[i][j] = -1;
		}
	}
}

int solve(int i, int residue) 
{
	if(-1 != record[i][residue])
		return record[i][residue];
	int result = 0;
	if(i >= N)
		return result;
	if(weight[i] > residue)
	{
		record[i + 1][residue] = solve(i+1, residue);
		
	}
	else 
	{
		result = max(solve(i+1, residue), solve(i+1, residue-weight[i]) + value[i]);
	}
	return record[i + 1][residue] = result;
}

int main() {
	init();
	int result = solve(0, W);
	cout << result << endl;
	return 0;
}