题目链接: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1085
题意: 中文题诶~
思路: 01背包模板题.
用dp[i][j]表示到第i个物品花去j空间能存储的最大价值, 那么很显然有
1 for(int i=1; i<=n; i++){
2 for(int j=0; j<=m; j++){ //注意这里的j是从0开始而非a[i]
3 if(j>=a[i]){
4 dp[i][j]=max(dp[i-1][j-a[i]]+b[i], dp[i-1][j]);
5 }else{
6 dp[i][j]=dp[i-1][j];
7 }
8 }
9 }
ac代码:
1 #include <bits/stdc++.h>
2 #define MAXN 110
3 #define MAN 10010
4 using namespace std;
5
6 int dp[MAXN][MAN]; //dp[i][j]表示到第i个物品花去j空间能存储的最大价值
7
8 int main(void){
9 int n, m, a[MAXN], b[MAXN]; //n为物品数量, m为背包容量, a, b分别存储物品的体积和价值
10 scanf("%d%d", &n, &m);
11 for(int i=1; i<=n; i++){
12 scanf("%d%d", &a[i], &b[i]);
13 }
14 memset(dp, 0, sizeof(dp));
15 for(int i=1; i<=n; i++){
16 for(int j=0; j<=m; j++){
17 if(j>=a[i]){
18 dp[i][j]=max(dp[i-1][j-a[i]]+b[i], dp[i-1][j]);
19 }else{
20 dp[i][j]=dp[i-1][j];
21 }
22 }
23 }
24 printf("%d\n", dp[n][m]);
25 return 0;
26 }
我们也可以只开一维数组, 用dp[j]表示花了j空间后最大可以装的价值
那么代码我们可以写成:
1 #include <bits/stdc++.h>
2 #define MAXN 10010
3 using namespace std;
4
5 int dp[MAXN]; //dp[j]表示花去j空间能存储的最大价值
6
7 int main(void){
8 int n, m, a[MAXN], b[MAXN]; //n为物品数量, m为背包容量, a, b分别存储物品的体积和价值
9 scanf("%d%d", &n, &m);
10 for(int i=1; i<=n; i++){
11 scanf("%d%d", &a[i], &b[i]);
12 }
13 memset(dp, 0, sizeof(dp));
14 for(int i=1; i<=n; i++){
15 for(int j=m; j>=a[i]; j--){ //这里是从后往前推的
16 dp[j]=max(dp[j-a[i]]+b[i], dp[j]);
17 }
18 }
19 printf("%d\n", dp[m]);
20 return 0;
21 }