|
有num个物品，总背包容量为Capacity, 求不超过背包总容量的前提下使得背包里的物品的价值达到最大的物品是哪些物品。
对于每个物品，只有两种选择，要么装要么不装进背包。
那么在考虑前 i 个物品时，在当前容量为 j 的条件下，如果这个物品的体积小于当前背包剩下体积，且装入此物品的价值比不装此物品的价值大，就装入此物品 ,设第 i 个物品的体积为 vol[ i ] ,价值 为 val [ i] ，result [ j ]表示容量为 j 时的价值，那么
result [ j ] = max{ result[ j ], result[ j - vol[ i ] ] + val[ i ]}, j>=vol[j]
如果 j < vol[ i ] ，说明当前的容量小于 当前物品的体积，肯放就是不放该物品了，那么在这个容量下的值就是不变的
这样对每个物品考虑完后，result [ Capacity ] 就是结果，
值得注意的是，求每个 result[ j ] 时，由于都只会访问
result [ k ] ,k<j, 所以求result[ j ] 时 ，用逆序，本质也就是如果一个物品放了一次，就不能再放第二次了。
空间复杂度是 o(Capacity),
代码如下：
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char** argv)
{
cout<<"0/1 背包问题"<<endl<<endl<<"输入背包总容量"<<endl;
size_t Capacity;
cin>>Capacity;
cout<<"输入物品总数目"<<endl;
size_t num;
cin>>num;
cout<<"输入物品的体积和价值"<<endl;
vector<int> vol;
vector<int> val;
int temp1,temp2;
int i=0,j=0;
for(i=0;i<num;++i)
{
cin>>temp1>>temp2;
vol.push_back(temp1);
val.push_back(temp2);
}
vector<int> result(Capacity+1,0);
int temp;
for(i=0;i<num;++i)
{
for(j=Capacity;j>=vol[i];--j)
{
temp = result [j-vol[i]] + val[i];
if(temp > result[j])
result[j] = temp;
}
}
cout<<"最大价值为 "<<result[Capacity]<<endl;
return 0;
}
运行结果
| 
转播
