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