背包问题
例题一
有 N件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 i件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤10000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8方法一：二维数组
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
//v[]体积 w[]价值
int f[N][N],v[N],w[N];
int main(){
//wm:最大容量
int n,vm;
cin>>n>>vm;
for(int i =1;i<=n;i++){
cin>>v[i]>>w[i];
}
for(int i =1;i<=n;i++){
for(int j =0;j<=vm;j++){
f[i][j] = f[i-1][j];
if(j>=v[i])
f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
}
}
cout<<f[n][vm];
return 0;
}方法二：一维数组
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N];
int main(){
//wm:最大容量
int n,vm,v,w;
cin>>n>>vm;
for(int i =1;i<=n;i++){
cin>>v>>w;
for(int j =vm;j>=v;j--){
f[j]= max(f[j],f[j-v]+w);
}
}
cout<<f[vm];
return 0;
}例题二
Hello Kitty想摘点花生送给她喜欢的米老鼠。
她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。
地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty只能向东或向南走，不能向西或向北走。
问Hello Kitty最多能够摘到多少颗花生。
输入格式
第一行是一个整数T，代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。
输出格式
对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。
数据范围
1≤T≤100,
1≤R,C≤100,
0≤M≤1000
输入样例：
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
输出样例：
8
16方法一：二维数组
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
//f[][]：最终结果 w[][]：花生数量
int f[N][N],w[N][N];
int main(){
int T,R,C;
cin>>T;
while(T--){
cin>>R>>C;
for(int i =1;i<=R;i++){
for(int j=1;j<=C;j++){
cin>>w[i][j];
}
}
for(int i =1;i<=R;i++){
for(int j =1;j<=C;j++){
f[i][j] = max(f[i-1][j],f[i][j-1])+w[i][j];
}
}
cout<<f[R][C]<<endl;
}
return 0;
}
方法一：一维数组
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N],w;
int main(){
int T,R,C;
cin>>T;
while(T--){
cin>>R>>C;
//清除上次的影响
memset(f,0,N);
for(int i =1;i<=R;i++){
for(int j=1;j<=C;j++){
cin>>w;
f[j] = max(f[j],f[j-1])+w;
}
}
cout<<f[C]<<endl;
}
return 0;
}例题三
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤1000，
−109≤数列中的数≤109−109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N],a[N];
int main(){
int n,res=0;
cin>>n;
for(int i =1;i<=n;i++){
cin>>a[i];
for(int j=i-1;j>=0;j--){
if(a[i]>a[j])f[i] = max(f[j],f[i]);
}
f[i]++;
res = max(res,f[i]);
}
cout<<res<<endl;
return 0;
}
