背包问题（01背包）
A-采药
题意：题目的意思很明确，药童上山采药，要你求在规定的时间内使采药的价值最大
题解：标准的0-1背包格式，每一件物品只有两种状态：选 or 不选；每一件物品只能用一次。
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int T,M;
int v[150]={0},p[150]={0};
ll f[1010]={0};
int main(){
cin>>T>>M;
for(int i=1;i<=M;i++){
cin>>v[i]>>p[i];
}
for(int i=1;i<=M;i++){
for(int j=T;j>=v[i];j--){
f[j]=max(f[j],f[j-v[i]]+p[i]);
}
}
cout<<f[T]<<endl;
return 0;
} B-开心的金明
题意：简单的0-1背包问题，但这里要我们求得是体积与价值的乘积和最大的值
题解：简单0-1背包
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int N,m;
int v[30]={0};
int p[30]={0};
ll num[30][30010]={0};
ll ans[30010]={0};
int main(){
cin>>N>>m/*m件物品*/;
//方法 一
for(int i=1;i<=m;i++){
cin>>v[i]>>p[i];
}//数据输入完毕，下面开始遍历背包
for(int i=1;i<=m;i++){
for(int j=N;j>=v[i];j--){
ans[j]=max(ans[j],ans[j-v[i]]+v[i]*p[i]);
}
}
//方法 二
// for(int i=1;i<=m;i++){
// for(int j=0;j/*这个相当于容量*/<=N;j++){
// num[i][j]=num[i-1][j];
// if(j>=v[i]){
// num[i][j]=max(num[i][j],num[i-1][j-v[i]]+v[i]*p[i]);
// }
// }
// }
// ll res=0;
// for(int i=0;i<=N;i++) res=max(res,num[m][i]);
// cout<<res<<endl;
cout<<ans[N]<<endl;
return 0;
} 
投递中汇等公司8个岗位 >
