@[Dream_Loner](/user/238711) 这题正解是背包吧
by Polaris_flame @ 2023-08-14 18:43:33
@[Polaris_flame](/user/1046448) 是，但是我在练 dfs 部分分，但我现在 0 pts
by Dream_Loner @ 2023-08-14 18:44:16
@[Dream_Loner](/user/238711) 这道题直接纯dfs就好了，直接递归，然后随便加个剪枝（记忆）就能过。
by da_ke @ 2023-08-14 20:04:33
dp!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
```cpp
#include <bits/stdc++.h>
using namespace std;
int a[1010], b[110], c[110];
int main(){
int n, t;
cin>>t>>n;
for (int i = 1;i<=n;i++){
cin>>b[i]>>c[i];
}
for (int i = 1;i<=n;i++){
for (int j = t;j>=b[i];j--){
a[j] = max(a[j],a[j-b[i]]+c[i]);
}
}
cout<<a[t];
return 0;
}
```
by Tx1234567 @ 2023-08-18 08:36:35
这题正解是背包，别的解得是大犇才能解出来
DP代码如下
```
#include<bits/stdc++.h>
using namespace std;
const int N=110,M=1010;
int n,m,dp[N][M];
int v[N],w[N];
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++){
dp[i][j]=dp[i-1][j];
if(j>=v[i])
dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
}
cout<<dp[n][m];
return 0;
}
```
by Ethan216 @ 2023-08-18 10:30:29
@[Dream_Loner](/user/238711)
这是我的程序。如果要 AC 的话需要加记忆化了
```cpp
ll dfs(int u, int k){
if(u <= 0 || k > m) return 0;
if(u < a[k].w) return dfs(u, k + 1);
ll sel = dfs(u - a[k].w, k + 1) + a[k].v,
unsel = dfs(u, k + 1);
return max(sel, unsel);
}
// main 函数
cin >> t >> m;
for(int i = 1; i <= m; i++){
cin >> a[i].w >> a[i].v;
}
cout << dfs(t, 1);
```
by PanDaoxi @ 2023-09-03 22:33:56