简简单单的背包

数组开小了直接7个E。。。 :(

01背包问题裸题

路过一只小渣逼

路过

200 8
79 83
58 14
86 54
11 79
28 72
62 52
15 48
68 62

#include <iostream>
#include <cstdio>
using namespace std;
int F(int a,int b)
{
if(a>b)return a;
else return b;
}
int main(void)
{ //freopen("medic.in","r",stdin);
//freopen("medic.out","w",stdout);
int n = 0,v = 0;int r[9000]={0},w[9000]={0};int f[400][400]={0};
cin>>v>>n;
for(int i = 1;i<n+1;i++)
{
cin>>r[i]>>w[i];
}
for(int i=1;i<n+1;i++)
for(int j = v;j>=r[i];j--)
{
f[i][j]=F(f[i-1][j],f[i-1][j-r[i]]+w[i]);
}
cout<<f[n][v];
}

蒟蒻第50道题留念。。

因为非常蠢的问题错了一次。
复习动态规划系列.....

shui

写记忆化搜索
一个>=写成了>
WA了一个点

还有第五种写法: DFS+剪枝
弱剪枝:前缀和计算从 ∑v[j] (i<=j<=n)
强剪枝:先按性价比排序,然后计算该条分枝的上界.

速度快的一比

[size=36]~\(≧▽≦)/~啦啦啦[/size]

回复 @星裔·自由蒂兰 :
天天开小号装萌新好玩不？。

01背包基础模板。。。