高校问答林心如只为遇见你图片:一个c++装箱问题
来源：百度文库 编辑：高校问答 时间：2024/05/02 04:46:02
#include<iostream>
using namespace std;
int v[1000];
int s(int w,int n)
{
if(w==0)
return 0;
if(n==0)
return w;
if(w-v[n]<0)
return s(w,n-1);
if(s(w-v[n],n-1)>s(w,n-1))//判断要不要将当前物品放入箱子中，怎么判断的？
return s(w,n-1);
else return s(w-v[n],n-1);
}
int main()
{
int i,w,n;
cin>>w;
cin>>n;
for(i=1;i<=n;i++)
cin>>v[i];
cout<<s(w,n);
system("pause");
return 0;
}
using namespace std;
int v[1000];
int s(int w,int n)
{
if(w==0)
return 0;
if(n==0)
return w;
if(w-v[n]<0)
return s(w,n-1);
if(s(w-v[n],n-1)>s(w,n-1))//判断要不要将当前物品放入箱子中，怎么判断的？
return s(w,n-1);
else return s(w-v[n],n-1);
}
int main()
{
int i,w,n;
cin>>w;
cin>>n;
for(i=1;i<=n;i++)
cin>>v[i];
cout<<s(w,n);
system("pause");
return 0;
}
s(w-v[n],n-1)是将当前物品装入箱子以后继续装箱最后箱子所剩空间
s(w,n-1)是不装入当前物品以后继续装箱最后箱子所剩空间
这个最好用个例子来理解
比如：
w=10,n=2,v[1]=6,v[2]=5
1)s(w,n)=s(10,2)
2)s(w-v[n],n-1)=s(10-v[2],1)=s(5,1)(此时又需判断，转3))
s(w,n-1)=s(10,1)（转4))
3)因w-v[n]=5-v[1]=-1<0，转s(w,n-1)=s(5,0)=5，箱子所剩空间为5
4)s(w-v[n],n-1)=s(10-v[1],0)=s(4,0)=4
s(w,n-1)=s(10,0)=10(4<10,v[1]装入，箱子所剩空间为4
因为5>4，所以v[2]没有装入