01背包类型问题

来源：百度知道 编辑：UC知道 时间：2024/09/24 17:18:43
有一个箱子容量为V（正整数，0≤V≤20000），同时有n个物品（0小于n≤30），每个物品有一个体积（正整数）。要求从n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入v，n，在输入n个物品的体积。
输出箱子的剩余空间为最小。

百科上有源码，但是明显是错的。。问下思路。。

其实就是n 个数中取若干个的组合，再从中选出符合条件的...
int f[20000]={0};
f[0]=1;//要初始化..
for(int i=0;i<n;i++)
for(int j=V;j>=v[j];j--) //因为是0-1,所以不能从小到大，否则一种被取了多次...
{
if(f[j-v[i]]==1) // f[j]=f[j-v[i]]==1?1:0; 当前的j能够由v[i]组合，则必须f[j-v[i]]==1.
f[j]=1;
}

for(int i=V;i>=0;i--)
if(f[i])cout<<i<<endl,break;