@[stripe_python](/user/928879) 得改成 “P1048 [NOIP2005 普及组] 采药/【模板】01 背包”，普及组的标签怎么能删掉呢？
by zhlzt @ 2023-05-05 21:30:08
@[stripe_python](/user/928879) 还有，“P1616 疯狂的采药” 照理来说应该要改成 “P1616 疯狂的采药/【模板】完全背包”
by zhlzt @ 2023-05-05 21:32:57
@[Special_Tony](/user/571147) 有道理
by stripe_python @ 2023-05-05 21:33:51
@[stripe_python](/user/928879) at 管理员吧
by zhlzt @ 2023-05-05 21:34:48
@[离散小波变换°](/user/68344)
by zhlzt @ 2023-05-05 21:35:12
@[stripe_python](/user/928879)
可是我01背包不行呀……
```
#include<cstdio>
using namespace std;
const int maxm=2001,maxn=31;
int m,n;
int w[maxn],c[maxn];
int f[maxn];
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&w[i],&c[i]);
for(int i=1;i<=n;i++)
for(int v=m;v>=w[i];v--)
if(f[v-w[i]]+c[i]>f[v]) f[v]=f[v-w[i]]+c[i];
printf("%d",f[m]);
return 0;
}
```
by lzh009 @ 2023-08-08 13:45:12
@[lzh009](/user/952814) maxn要开100级的
by stripe_python @ 2023-08-08 14:31:55
@[stripe_python](/user/928879)
谢谢
by lzh009 @ 2023-08-08 15:18:13
@[stripe_python](/user/928879)
搜索也能过……
```
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 105;
int n, m, ans;
struct Node {
int a, b; // a 代表时间，b 代表价值
double f;
} node[N];
bool operator<(Node p, Node q) { return p.f > q.f; }
int f(int t, int v) { // 计算在当前时间下，剩余物品的最大价值
int tot = 0;
for (int i = 1; t + i <= n; i++)
if (v >= node[t + i].a) {
v -= node[t + i].a;
tot += node[t + i].b;
} else
return (int)(tot + v * node[t + i].f);
return tot;
}
void work(int t, int p, int v) {
ans = max(ans, v);
if (t > n) return; // 边界条件：只有n种物品
if (f(t, p) + v > ans) work(t + 1, p, v); // 最优性剪枝
if (node[t].a <= p) work(t + 1, p - node[t].a, v + node[t].b); // 可行性剪枝
}
int main() {
scanf("%d %d", &m, &n);
for (int i = 1; i <= n; i++) {
scanf("%d %d", &node[i].a, &node[i].b);
node[i].f = 1.0 * node[i].b / node[i].a; // f为性价比
}
sort(node + 1, node + n + 1); // 根据性价比排序
work(1, m, 0);
printf("%d\n", ans);
return 0;
}
```
by lzh009 @ 2023-08-09 08:26:25