动态规划经典题

题干如下:

给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.

输入:

  • 第一行包含两个整数n, m分别表示物品的个数和背包能装重量。
  • 以后N行每行两个数Wi和Vi,表示物品的重量和价值

输出:

  • 输出1行,包含一个整数,表示最大价值。

样例输入:

1
2
3
4
3 5
2 3
3 5
4 7

样例输出:

1
8

思路如下:

w[j] -> 物品体积
v[j] -> 物品价值

边界:

1
2
Fun[i][0] = 0;
Fun[0][j] = 0;

i: 当前剩余容积

j: 前j件物品

Fun[i][j]: 容积i,前j件物品最优解

状态转移方程:

1
Fun[i][j] = max(Fun[i][j-1] , Fun[i-w[j]][j-1] + v[j])

题解如下:

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;
int w[1005];
int v[1005];
int Fun[1005][1005];
int main(){
int n,m;
/*-----数据录入-----*/
cin >> n >> m;
for(int i = 1; i<=n; i++){
cin >> w[i] >> v[i];
}
/*-----边界初始化-----*/
for(int i = 0; i<=n; i++){
Fun[0][i] = 0;
Fun[i][0] = 0;
}
/*-----递推式动规-----*/
for(int i = 1; i <= m; i++){
for(int j = 1;j <= n; j++){
Fun[i][j]=Fun[i][j-1];
if(w[j] <= i)
Fun[i][j] = max(Fun[i][j-1] , Fun[i-w[j]][j-1] + v[j]);
}
}
/*-----输出结果----*/
cout<< Fun[m][n] <<endl; //Prints:8
return 0;
}