题解 | #[NOIP2001]装箱问题#
[NOIP2001]装箱问题
https://www.nowcoder.com/practice/55100a6608ad4656849dbd1f16d044cb
#include<iostream> #include<vector> using namespace std; int main(){ int weight,n,maxw=0; cin>>weight>>n; int w[n]; for(int i=0;i<n;i++) cin>>w[i]; vector<int> dp(weight+1,0); for(int i=0;i<n;i++) for(int j=weight;j>=w[i];j--) { dp[j]=max(dp[j],dp[j-w[i]]+w[i]); maxw=max(maxw,dp[j]); } cout<<weight-maxw<<endl; } //dp[i][j]:把前i件物品放进总重为j的背包的最大重量 //动态转移方程:dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+w[i]) //空间优化:滚动数组dp[j]=max(dp[j],dp[j-w[i]]+w[i])