装箱问题的三种解法

有一个箱子容量为V（正整数，0≤v≤20000），同时有n个物品（0< n ≤30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

样例

输入样例

输出样例

方法一：动规

dp[j]表示体积为j用掉的最大体积

动态转移方程：dp[j]=max(dp[j],dp[j-a[i]]+a[i]);

dp[j-a[i]]+a[i]表示a[i]全部装入

dp[j]表示不放入

#include<iostream>
#include<algorithm>
using namespace std;
int main(){int V,n,i,j;cin>>V>>n;int a[35]={};for(i=0;i<n;i++){cin>>a[i];}int dp[20005]={};for(i=0;i<n;i++){for(j=V;j>=a[i];j--){dp[j]=max(dp[j],dp[j-a[i]]+a[i]);}}cout<<V-dp[V]<<endl;
}

方法2 回溯

#include<iostream>
#include<algorithm>
using namespace std;
int a[35]={}; 
//maxV表示消耗的最大体积 
int maxV=0,n,V;
//sumV为实际消耗的体积 
//cnt为搜索的第cnt个物品 
void dfs(int cnt,int sumV){if(sumV>V)return;//搜索到最后一个 if(cnt==n+1){if(sumV>maxV)maxV=sumV;return; }//不放入 dfs(cnt+1,sumV);//全部放入 dfs(cnt+1,sumV+a[cnt]);
}
int main(){cin>>V;int i,j;cin>>n; for(i=0;i<n;i++){cin>>a[i]; }dfs(0,0);cout<<V-maxV<<endl;
}

方法3 贪心

从大到小排序，每次选择可以装入的

#include<iostream>
#include<algorithm>
using namespace std;
//从大到小排序 
int cmp(const void *a,const void *b){return *(int*)b-*(int*)a;
} 
int main(){int V,n,i,j;cin>>V>>n;int a[35]={};for(i=0;i<n;i++){cin>>a[i];}qsort(a,n,sizeof(int),cmp);for(i=0;i<n;i++){if(V==0)break;if(V>=a[i])V-=a[i]; }cout<<V<<endl; 
}

这样子有局限性，只有数组最大值放入能够使剩余空间最小才满足。

举个例子