01背包变题 | #装箱问题#
装箱问题
https://www.nowcoder.com/practice/c990bd0bf8e04bfbb19c0964401c8f77
#include <bits/stdc++.h>
using namespace std;
/**
有一个箱子容量为 V ，同时有n个物品，每个物品有一个体积（正整数）。每个物品只能使用一次。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
*/
int main()
{
int V,n;
cin>>V>>n;
vector<int> a(n);
int no = 0;
vector<int> dp(V+1,no);
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++) {
for(int j=V;j>=a[i];j--)
dp[j] = max(dp[j],dp[j-a[i]]+a[i]);
}
cout << V- dp[V] <<endl;
return 0;
}
算法常用解题技巧 文章被收录于专栏
算法常用解题技巧
OPPO公司福利 1135人发布