洛谷p1478-陶陶摘苹果（升级版）

, ,

题目链接

题解一：
可以使用动态规划来解决此类问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream> 
using namespace std;
int dp[5005][1001];
int xi[5005],yi[5005],n,s,a,b;
int main(){
    cin>>n>>s>>a>>b;
    for(int i=1;i<=n;i++){
        cin>>xi[i]>>yi[i];
    }
    for(int i=1;i<=n;i++)//枚举考虑每一个苹果
    for(int j=0;j<=s;j++){//枚举背包大小
        dp[i][j]=dp[i-1][j];//不能取就直接转移考虑之前苹果的最大值
        if(xi[i]<=a+b&&j>=yi[i])//如果能够取
        dp[i][j]=dp[i-1][j-yi[i]]+1>dp[i][j]?dp[i-1][j-yi[i]]+1:dp[i][j];//动态转移方程
    }
    cout<<dp[n][s];//因为是从前向后递推，因此接收最终答案的位置也从最前面转到了最后面
    return 0;
}

其中的动态转移方程，如果能够取苹果的话，判断:
dp[i][j]=dp[i-1][j-yi[i]]+1>dp[i][j]?dp[i-1][j-yi[i]]+1:dp[i][j]

首先：
取苹果是：dp[i-1][j-yi[i]]+1。
取苹果了，那么力气就减少对应摘这个苹果需要消耗的体力，即j-yi[i]。
空间也减小了，即i-1(因为题目中没有说不同苹果所占空间不一样，所以每个苹果人为占1空间)。
取苹果了，那么现在的背包中的苹果的总价值也要加一，即dp[][]+1(因为题目中只问了能取多少个苹果，所以，就相当于每个苹果的价值为都为1)。

不取苹果是：dp[i][j]，即不需要更新这个数组。

其中，不仅枚举考虑每一个苹果的大小，还枚举了背包的大小，这是为什么呢？？？