最少数量货物装箱问题
最少数量货物装箱问题
http://www.nowcoder.com/questionTerminal/37aa8a88a72e47f798a14d63bee61d8f
题目难度：二星
考察点：动态规划
方法1：暴力
1. 分析：
这道题类似于完全背包问题，每个货物都可以无限使用，但是要求背包必须装满，而且要求背包中的物品数目最少。由于货物是无限的，那么假设dp[n]表示背包容量为n的能够装满的最少货物个数，如果选择3, 5, 7任意的一种货物重量，那么dp[n-3]、dp[n-5]、dp[n-7]就会是背包容量为n的一种选择，所以问题就转化为了求dp[n-x]，其中x=3、5、7，那么这就是一个递归求解的问题。举个例子：n=8,求dp[8]
那么dp[8] = min(dp[8-3], dp[8-5], dp[8-7]) + 1 = min(dp[5], dp[3], dp[1]) + 1
其中dp[5] = min(dp[5-3], dp[5-5]) + 1 = min(dp[2], dp[0]) + 1 = 1
其中dp[3] = dp[3-3] + 1 = dp[0] + 1 = 1
在递归回去得到dp[8] = min(1, 1, INF) + 1 = 2,所以dp[8] = 2
2. 复杂度分析：
时间复杂度：O(n^3)空间复杂度：O(1)
3. 代码：
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int dfs(int x) {
if(x == 0) return 0;
if(x < 0) return INF;
int ans = INF;
ans = min(dfs(x-3), min(dfs(x-5), dfs(x-7)))+1;
return ans;
}
int main() {
int n; cin>>n;
int ans = dfs(n);
cout<<(ans>=INF?-1:ans)<<endl;
return 0;
} 方法2：动态规划
1. 分析：
由于上述递归的复杂度太高，我们可以采用动态规划的算法来进行考虑，即把上述的递归改成递推，递推方程已经在上述的方法中列出来了，即dp[i] = min(min(dp[i-3],dp[i-5]),dp[i-7])+1，所以直接进行计算，最后输出dp[n]即可。 算法实现：
(1). 输入背包容量n
(2). 预处理dp数组为最大值
(3). 预处理i=3,5,,6,7的时候dp[i]的值,即 dp[3] = dp[5] = dp[7] = 1， dp[6] = 2;
(4). 根据递推方程进行遍历求解，最后输出结果dp[n]
2. 复杂度分析：
时间复杂度：O(n)空间复杂度：O(n)
3. 代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4+5;
int dp[MAXN];
int main() {
int n; cin>>n;
for(int i=1; i<=n; i++) dp[i] = n+1;
dp[3] = dp[5] = dp[7] = 1;
dp[6] = 2;
for(int i=8; i<=n; i++) dp[i] = min(min(dp[i-3],dp[i-5]),dp[i-7])+1;
cout<<(dp[n]==n+1?-1:dp[n])<<endl;
return 0;
}
