算法练习题——0 1背包问题

86 阅读 0 评论 57 点赞

我是靠谱客的博主彩色花生，这篇文章主要介绍算法练习题——0 1背包问题，现在分享给大家，希望可以做个参考。

时间限制： 2 S 内存限制： 128 MB

题目描述：


给你一个固定容量的背包v，和n个物品。每个物品有它的体积和价值，每个物品只能拿1个，在总物品的体积不超过背包容量的前提下可以获得的最大价值。

输入：


第一行输入两个int型整数v和n,表示背包的容量和给出的物品数。(v<=1000,n<=100)然后给出n个物品，vi和mi表示物品的体积和价值。(1<=vi<=mi<=1000)

输出：


输出一个整数表示所能得到的最大价值并换行。

样例输入：

样例输出：

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;
}