朴素二维01背包问题
分析
- 状态表示
f[i, j]
- 集合:从前i个物品中选,且总体积不超过j的选法的剩余空间的集合
- 属性:题目要使箱子的剩余空间为最小,故属性为最小值->取
min()
- 状态计算
f[i-1, j]
表示不选第i个物品f[i-1, j-v] - v
表示选第i个物品,则要减去此物品的体积v(因为是求剩余空间)- 因此
f[i, j] = min(f[i-1, j], f[i-1, j-v]-v)
注意:二维空间下,dp数组占用空间为20000*20000*4B = 1600MB
,远远大于题目64MB的限制,提交显示Runtime Error
代码如下
#include <iostream>
using namespace std;
const int N = 2e4+5;
int av, n;
int f[N][N];
int v;
int main()
{
cin >> av >> n;
for(int i=0; i<=n; i++)
f[i][0] = av;
for(int i=0; i<=av; i++)
f[0][i] = av;
for (int i = 1; i <= n; ++i)
{
cin >> v;
for(int j=0; j<=av; j++)
{
f[i][j] = f[i-1][j];
if(j >= v)
f[i][j] = min(f[i][j], f[i-1][j-v]-v);
}
}
cout << f[n][av] << endl;
return 0;
}
优化成一维
沿用经典01背包问题的优化思路即可
代码如下
#include <iostream>
using namespace std;
const int N = 2e4+2;
int av, n;
int f[N];
int v;
int main()
{
cin >> av >> n;
for(int i=0; i<=av; i++)
f[i] = av;
for (int i = 1; i <= n; ++i)
{
cin >> v;
for(int j=av; j>=v; j--)
f[j] = min(f[j], f[j-v]-v);
}
cout << f[av] << endl;
return 0;
}