题目描述
有 NN 件物品和一个容量是 VV 的背包。每件物品只能使用一次。
第 ii 件物品的体积是 vivi,价值是 wiwi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行两个整数,N,VN,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 NN 行,每行两个整数 vi,wivi,wi,用空格隔开,分别表示第 ii 件物品的体积和价值。
输出格式
输出一个整数,表示最大价值。
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例
8
算法
就是为了学习贪心算法,不过很多写算法的人不注意命名规范,还喜欢用全局变量,这习惯不好,打代码最重要的就是美观了。
C++ 代码
#include <iostream>
#include<string.h>
using namespace std;
int main()
{
int N,V;
cin>>N>>V;
int* value=new int[(N+1)*(V+1)];
memset(value,0,sizeof(int)*(N+1)*(V+1));
for (int i = 1; i < N+1; i ++ )
{
int volumn,worth;
cin>>volumn>>worth;
for (int j = 0; j < V+1; j ++ )
{
if(j<volumn)value[i*(V+1)+j]=value[(i-1)*(V+1)+j];
else if(j>=volumn)value[i*(V+1)+j]=max(value[(i-1)*(V+1)+j-volumn]+worth,value[(i-1)*(V+1)+j]);
}
}
cout<<value[N*(V+1)+V];
return 0;
}