[01背包1.0 关键代码] [c++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| int dfs(int x ,int spV, int sumW)
{
if(x>n) return 0;
else if(spV<v[x]) return dfs(x+1,spV,sumW);
else if(spv>=v[x])
{
return max(dfs(x+1,spV,sumW),dfs(x+1,spV-v[x],sumW+w[x]));
}
}
//记忆化搜索后
int dfs(int x ,int spV) //sumW不影响边界 抹去
{
if(mem[x][spV]) return mem[x][spV];
int sum=0;
if(x>n) sum= 0;
else if(spV<v[x]) sum= dfs(x+1,spV,sumW);
else if(spv>=v[x])
{
sum=max(dfs(x+1,spV,sumW),dfs(x+1,spV-v[x],sumW+w[x]));
}
mem[x][spV]=sum;
return sum;
}
//递推
for(int i=n;i>=1;i--) //从底部开始
{
for(int j=0;j<=m;j++)
{
if(j<v[i]) f[i][j]=f[i+1][j];
else f[i][j]=max(f[i+1][j],f[i+1][j-v[i]]+w[i]);
//就是直接dfs方程复制过来
}
}
cout<<f[1][m]; //终点是这个 第一个物品 体积是满的
|
当然可以优化成一维 我们只需要注意一个问题
为什么二维不用倒序 一维必须倒序呢?
十分简单的一个道理
由f[i][j]=max(f[i+1][j],f[i+1][j-v[i]]+w[i]) 此时的f[x][y]需是当前状态
若0-v枚举 如:i i i (i-1 i-1 i-1)
括号内是未更新的状态
若v-0枚举则规避了这个问题
[洛谷1048采药(01背包一维优化)] [c++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include<bits/stdc++.h>
using namespace std;
int n,m;
int t[10010],w[10010];
int f[100];
int main()
{
cin>>n>>m; //n是时间 m是数量
for(int i=1;i<=m;i++) cin>>t[i]>>w[i];
for(int i=m;i>=1;i--)
{
for(int j=n;j>=t[i];j--)
{
if(j<t[i]) f[j]=f[j];
else if(j>=t[i])
{
f[j]=max(f[j],f[j-t[i]]+w[i]);
}
}
}
cout<<f[n]<<endl;
}
|
[] [c++]
