背包骚操作--DP数组的再利用
白书上给了个目前没什么用的解法,用dp[0][j]和dp[1][j]保存两个状态,利用&运算符不停滚动更新,这个虽然不如一维的开销小,但是以后也许会用的到,思路奇妙#include<iostream>#include<cstring>#include<cstdio>#include<a
·
白书上给了个目前没什么用的解法,用dp[0][j]和dp[1][j]保存两个状态,利用&运算符不停滚动更新,这个虽然不如一维的开销小,但是以后也许会用的到,思路奇妙
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
int main()
{
int t, n;
int dp[2][1005]; //两个滚动数组
int w[105], v[105];
scanf("%d%d", &t,&n);
for(int i = 1; i <= n; i ++)
scanf("%d%d", &w[i], &v[i]);
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i ++)
for(int j = 0; j <= t; j ++)
{
if(j < w[i])
dp[i & 1][j] = dp[(i - 1) & 1][j];
else dp[i & 1][j] = max(dp[(i - 1) & 1][j], dp[(i - 1) & 1][j - w[i]] + v[i]);
}
printf("%d\n", dp[n & 1][t]);
return 0;
}
更多推荐
已为社区贡献6条内容
所有评论(0)