题目描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数,表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
样例
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
8
二维算法
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int p=1010;
int n,m;
int v[p],w[p];//v数组表示第i件物品的体积,w数组表示第i件物品的价值
int f[p][p];//f数组表示前i件物品,背包容量j下的价值的最大值
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];//输入数据
}
for(int i=1;i<=n;i++)//前i件物品
{
for(int j=0;j<=m;j++)//背包的空间
{
f[i][j]=f[i-1][j];
if(j>=v[i])//背包可以放下第i件物品
f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
cout<<f[n][m];
return 0;
}
一维算法
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int p=1010;
int n,m;
int v[p],w[p];//v数组表示第i件物品的体积,w数组表示第i件物品的价值
int f[p];//f数组表示N件物品,背包容量j下的价值的最大值
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];//输入数据
}
for(int i=1;i<=n;i++)//前i件物品
{
for(int j=m;j>=v[i];j--)//只有当j>v[i]才会更新,注意j从m开始,因为从小到大的话会使上一层的被覆盖,导致更新这一层时出错
//因为如果j<v[i],f[i][j]=f[i-1][j]改为了f[j]=f[j],所以此步可以省略只考虑v>=v[i]的情况;
//当j>=v[i]时,f[i][j]=max(f[i)[j],f[i-1][j-v[i]+w[i])改为了f[j]=(f[j],f[j-v[i]+w[i])
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m];
return 0;
}