dp问题
满足最优子结构：不管过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。
无后效性：以前各阶段的状态无法直接影响它未来的决策。
背包问题
有 N件物品和一个容量是 V的背包。每件物品只能使用一次。
第 i 件物品的体积是 v_i，价值是 w_i。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 v_i, w_i，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <iostream>
using namespace std;
int n,m;
int w[1010],v[1010];
int f[1010][1010];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
if(j<w[i]) f[i][j]=f[i-1][j];
else{
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
}
}
}
cout<<f[n][m];
return 0;
}
|
当每种类别有s个物品,多重背包问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int f[N][N]={};
int s[N],v[N],w[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i]>>s[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=1;k<=s[i];k++){
if(j<k*v[i]) f[i][j]=f[i-k][j];
else f[i][j]=max(f[i-1][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
}
cout<<f[n][m];
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int f[N][N];
int a[N][N];
int n,m;
int main(){
int t;
cin>>t;
while(t--){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<m;j++){
f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
}
}
cout<<f[n-1][m-1]<<endl;
}
return 0;
}
|
偷商店
阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N 家店铺，每家店中都有一些现金。
阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。
他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金?
输入格式
输入的第一行是一个整数 T，表示一共有 T 组数据。接下来的每组数据，第一行是一个整数 N ，表示一共有 N 家店铺。第二行是 N 个被空格分开的正整数，表示每一家店铺中的现金数元。
每家店铺中的现金数量均不超过1000。
imput tamples:
2
3
1 8 2
4
10 7 6 14
result:
8
24
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int rob(vector<int>& money){
int dp[200]={};
dp[0]=money[0];
int n=money.size();
for(int i=1 ;i<n;++i){
if(i==1){
dp[1]=max(money[0],money[1]);
}
else{
dp[i]=max(dp[i-1],dp[i-2]+money[i]);
}
}
return dp[n-1];
}
int main(){
int n;
cin>>n;
vector<int> money;
vector<vector<int> > group;
int i;
int tem=n;
vector<int> res;
int a[50];
while(tem!=0){
cin>>a[tem];
while (cin>>i){
money.push_back(i);
if(cin.get()=='\n') break;
}
group.push_back(money);
money.clear();
tem--;
}
while(tem!=n){
res.push_back(rob(group[tem]));
tem++;
}
vector<int>::iterator it;
for(it=res.begin();it!=res.end();++it)
cout<<*it<<endl;
return 0;
}
|
地宫取宝
X 国王有一个地宫宝库，是 n×m个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是 k
件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 k件宝贝。
输入格式
第一行 3
个整数，n,m,k
，含义见题目描述。
接下来 n
行，每行有 m
个整数 Ci
用来描述宝库矩阵每个格子的宝贝价值。
输出格式
输出一个整数，表示正好取 k
个宝贝的行动方案数。
该数字可能很大，输出它对 1000000007
取模的结果。
数据范围
1≤n,m≤50
,
1≤k≤12
,
0≤Ci≤12
![]/img/(image-4.png)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=55, MOD =100000007;
int n,m,k;
int w[N][N];
int f[N][N][13][14];
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>w[i][j];
w[i][j]++;
}
}
f[1][1][1][w[1][1]]=1;
f[1][1][0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int u=0;u<=k;u++){
for(int v=0;v<=13;v++){
int &val=f[i][j][u][v];
val=(val+f[i-1][j][u][v])%MOD;
val=(val+f[i][j-1][u][v])%MOD;
if(u>0&& v==w[i][j]){
for(int c=0;c<v;c++){
val=(val+f[i-1][j][u-1][c])%MOD;
val=(val+f[i][j-1][u-1][c])%MOD;
}
}
}
}
}
}
int res=0;
for (int i=0;i<=13;i++) res=(res+f[n][m][k][i])%MOD;
cout<<res;
return 0;
}
|