时间限制：
2 S
内存限制：
128 MB
题目描述：
给你一个固定容量的背包v，和n个物品。每个物品有它的体积和价值，每个物品只能拿1个，在总物品的体积不超过背包容量的前提下可以获得的最大价值。
输入：
第一行输入两个int型整数v和n,表示背包的容量和给出的物品数。(v<=1000,n<=100)然后给出n个物品，vi和mi表示物品的体积和价值。(1<=vi<=mi<=1000)
输出：
输出一个整数表示所能得到的最大价值并换行。
样例输入：
100 5
77 92
22 22
29 87
50 46
99 90
样例输出：
133
Language: C++
#include <iostream>#include<fstream>
#include<algorithm>
#include<vector>
typedef struct item
{
int vi;
int mi;
}item;
using namespace std;
int max(int x,int y){
int temp = 0;
if(x>y) temp=x;
else temp=y;
return temp;
}
int main()
{
int v;
int n;
cin>>v>>n;
vector<vector<int> > k(v+1,vector<int>(n+1));
item items[100];
for(int i=0;i<n;i++){
cin>>items[i].vi;
cin>>items[i].mi;
}
for(int w=0;w<=v;w++)
{
for(int j=0;j<=n;j++)
{
k[w][j]=0;
}
}
for(int w1 = 1;w1<=v;w1++)
{
for(int j=1;j<=n;j++)
{
if(items[j-1].vi>w1)
{
k[w1][j]=k[w1][j-1];
}
else
{
k[w1][j]=max(k[w1][j-1],(k[w1-items[j-1].vi][j-1]+items[j-1].mi));
}
}
}
cout<<k[v][n]<<endl;
return 0;
}