0-1背包(滚动数组)
0-1背包使用滚动数组
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MIN = 0x80000000;
const int N = 3;//物品数量
const int V = 5;//背包容量
int f[V+1];
int Package(int *W, int *C, int N, int V);
int main()
{
int W[4] = {0, 7, 5, 8};//权重
int C[4] = {0, 2, 3, 4};//大小
int result = Package(W, C, N, V);
if(result>0)
{
cout << endl;
cout << "the opt value:" << result << endl;
}
else
cout << "can't find the opt value" << endl;
return 0;
}
int Package(int *W, int *C, int N, int V)
{
int i, j;
memset(f, 0, sizeof(f));
for(i=1; i<=V; i++)
f[i] = MIN;
for(i=1; i<=N; i++)
for(j=V; j>=C[i]; j--)
{
f[j] = (f[j]>f[j-C[i]]+W[i])?f[j]:(f[j-C[i]]+W[i]);
cout << "f[" << i << "][" << j << "]=" <<f[j] <<endl;
}
return f[V];
}
/*
f[1][5]=-2147483641
f[1][4]=-2147483641
f[1][3]=-2147483641
f[1][2]=7
f[2][5]=12
f[2][4]=-2147483641
f[2][3]=5
f[3][5]=12
f[3][4]=8
the opt value:12
*/