今日学习记录
1. 机器人饲养指南csp.37.1
关键词：背包
问题分析：
- 就是每天限制吃多少苹果,然后总要吃 n 个苹果,每天吃不同数量的苹果增加不同的值,要求怎样吃最大
核心思路
- 就是分组背包,每天的限制数量就是组,但是依旧先从 dfs+记忆化开始,如果是单纯的 dfs,可以定义 dfs(i,s),i 为苹果总数,s 为增加的值,那么这样做就是遍历每一种的最大情况,肯定超时,但是照我这样定义是不能记忆化的,因为每一个 i 和 s 对都是单独的情况,可以说就是暴力遍历,所以要想记忆化就得重新定义 dfs 的状态,从核心底层思想开始思考,从主问题向子问题思考,求 n 位置的最大值,那么肯定是在 n-1 的数值上继续选大的,那么 n-1 位置就是这个之前最大值,那么子问题就分析出来了,重新定义 dfs(i)为从 0 到 i 的最大值,这时会有很多情况会遍历到重复的 i 位置,但是每次我只选择记忆中的最大值就行,说实话写代码真不难,主要是这个状态要抓准
#include<iostream>
#include<vector>
using namespace std;
const int N = 10001;
vector<int> memt(N,-1);
int n,k;
int dfs(vector<int>& arr,int i){
if(i==0) return 0;
int &res = memt[i];
if(res!=-1) return res;
int ans = 0;
for(int x = 1;x<=min(i,k);x++){
ans = max(ans,dfs(arr,i-x)+arr[x-1]);
}
res = ans;
return ans;
}
int main(){
cin>>n>>k;
vector<int> arr(k);
for(int i = 0;i<k;i++){
cin>>arr[i];
}
cout<<dfs(arr,n);
return 0;
} - 记忆化出来之后再 1 变成递推
#include<iostream>
#include<vector>
using namespace std;
int n,k;
int main(){
cin>>n>>k;
vector<int> arr(k);
for(int i = 0;i<k;i++){
cin>>arr[i];
}
vector<int> dp(n+1);
dp[0] =0;
for(int i = 1;i<=n;i++){
for(int x = 1;x<=min(i,k);x++){
dp[i] = max(dp[i],dp[i-x]+arr[x-1]);
}
}
cout<<dp[n];
return 0;
} 说实话,我还是不明白分组背包是什么,原本看来是分组,但是现在做出来也没看到分组 学到的点：
- 动规