【问题描述】

给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，问如何选择装入背包的物品，使得装入容量为c的背包的物品的总价值最大？

【输入形式】

第一行输入背包容量c；第二行输入要装入的物品的个数；第三行输入装入的各个物品的重量w[i]；第四行输入装入的物品的价值v[i]

【输出形式】

输出背包的最大总价值

【样例输入】

6
5
3 2 1 4 5
25 20 15 40 50

【样例输出】

65

c++代码

#include<iostream>
#include<algorithm>
using namespace std;
int V[100][100] = { 0 }; //造表记录子问题的最优解
int Knapsack(int w[], int v[], int n, int C);//实际物品数目，背包容量
int main()
{
	int C;
	cin>>C;
	int n;
	cin>>n;
   int w[100]={0}; 
   int v[100]={0};
   for (int i=1;i<=n;i++)
   {
   		cin>>w[i];
	}   
	for (int i=1;i<=n;i++)
	{
		cin>>v[i];
	}
   int maxValue = Knapsack(w, v, n, C);
   cout << maxValue;
    return 0;
}
int Knapsack(int w[], int v[], int n, int C) {
   for (int i = 0; i <= n; ++i)
      V[i][0] = 0;
   for (int j = 0; j <= C; ++j)
      V[0][j] = 0;
   for(int i=1;i<=n;++i)
      for (int j = 1; j <= C; ++j)
      {
         if (j < w[i])
            V[i][j] = V[i - 1][j];
         else {
            V[i][j] = max(V[i - 1][j], V[i - 1][j - w[i]] + v[i]);
         }
      }
   return V[n][C];
}