423. 采药
?输入样例：
70 3
71 100
69 1
1 2输出样例：
3题解：
非常简单的01背包问题，把时间看作背包容量，采集草药需要花费的时间看作是物体的体积，草药的价值看作是物体的价值
状态表示: f[i][j]-->在背包容量不超过? j 的条件下，从前 i 个物品选取所能获得的最大值
状态转移:不选第 i 个物品：f[i-1][j]
? ? ? ? ? ? ? ? ? ?选第 i 个物品：f[i-1][j-v[i]]
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + val[i]);
优化为一维背包：
f[j] = max(f[j], f[j - v[i]] + val[i]);AC代码：
#include<iostream>
using namespace std;
int T,M;
int tim[110],val[110];
int f[1010];
int main(){
cin>>T>>M;
for(int i=1;i<=M;i++){
cin>>tim[i]>>val[i];
}
for(int i=1;i<=M;i++){
for(int j=T;j>=tim[i];j--){
f[j]=max(f[j],f[j-tim[i]]+val[i]);
}
}
cout<<f[T]<<endl;
}1024. 装箱问题
?输入样例：
24
6
8
3
12
7
9
7输出样例：
0题解：
和上一题差不多，就是思维转一下，看代码
AC代码：
#include<iostream>
using namespace std;
int v, n;
int a[35];
int f[200010];
int main() {
f[0] = 1;
cin >> v >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
for (int j = v; j >= a[i]; j--) {
f[j] = max(f[j], f[j - a[i]]);
}
}
for (int i = v; i >= 0; i--) {
if (f[i]) {
cout << v - i << endl;
return 0;
}
}
}1022. 宠物小精灵之收服
?
?输入样例1：
10 100 5
7 10
2 40
2 50
1 20
4 20输出样例1：
3 30输入样例2：
?
10 100 5
8 110
12 10
20 10
5 200
1 110输出样例2：
0 100题解：
这题的题目比较长，读起来很烦，要耐心读题。
题目大意就是：输入N（花费1），M（花费2），K（K组数据，V1，V2）。
花费1：精灵球的数量
花费2：皮卡丘体力值
价值：小精灵数量
在花费1不超过N且花费2不超过M的前提下，所能获得的最大数量的小精灵
状态表示：f[i][j][k]：只从前 i 个物品选，且花费1不超过 j ，花费2不超过 k，能获得的最多的小精灵数量
状态转移：
f[i][j][k] = max(f[i - 1][j][k], f[i - 1][j - v1[i]][k - v2[i]] + 1);
优化为二维：
f[j][k] = max(f[j][k], f[j - v1[i]][k - v2[i]] + 1);那么答案就是：
最多收服的小精灵数量：f[K][N][M]--->f[N][M]（优化后）
最少消耗体力：f[K][N][min]==f[K][N][M]--->f[N][min]==f[N][M]（优化后）
AC代码：
#include<iostream>
using namespace std;
int N, M, K;
int v1[110], v2[110];
int f[1010][510];
int main() {
cin >> N >> M >> K;
for (int i = 1; i <= K; i++) {
cin >> v1[i] >> v2[i];
}
for (int i = 1; i <= K; i++) {
for (int j = N; j >= v1[i]; j--) {
for (int k = M - 1; k >= v2[i]; k--) {
//这里大家一定要注意
//因为当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤）
//而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。
//所以当我们把这个问题看作背包问题的时候，容量2只有M-1
f[j][k] = max(f[j][k], f[j - v1[i]][k - v2[i]] + 1);
}
}
}
cout << f[N][M - 1] << " ";//容量2为M-1
for (int i = 0; i <= M - 1; i++) {
if (f[N][i] == f[N][M - 1]) {
cout << M - i << endl;
return 0;
}
}
}