首先,这是经典的01背包问题
按照正常思路来写的话
两重循环,并且空间优化成一维,没有问题
但问题是,这题的M = 365 * 24 * 60,会超时
所以不能按照正常的写法来写
那么怎么优化呢?
01背包没有其它写法,最终还是只能这样写,只能选择更换体积和价值的位置
让体积去充当价值,价值反过来充当体积
- 原f[i][j]表示:从前i件物品里选,总体积不超过j时所能获得的最大价值
- 现f[i][j]表示:从前i件物品里选,总价值不超过j时所需要的最小背包体积
那么要想求n件物品的价值最大,就求最大价值时体积最小就行了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e3 + 10;
const int M = 3e4 + 10;
int v[N],w[N],f[M];
int main()
{
int n,m;
cin >> n >> m;
for(int i = 1;i <= n;i ++)
cin >> v[i];
int sum = 0;
for(int i = 1;i <= n;i ++)
{
cin >> w[i];
sum += w[i];
}
memset(f,0x3f,sizeof(f));
f[0] = 0;
for(int i = 1;i <= n;i ++)
for(int j = sum;j >= w[i];j --)
f[j] = min(f[j],f[j - w[i]] + v[i]);
for(int i = sum;i >= 0;i --)
if(f[i] <= m)
{
cout << i;
return 0;
}
}
这个比赛是在哪里参加呀
学校报名的,个人貌似没法报名
好吧~~