A79.装箱问题 题解

很正常的01背包，动态公式为 dp[j]=dp[j-w[i]]+w[i]
上代码——

#include<bits/stdc++.h>
using namespace std;
int dp[20002],w[40];
int m,n;
int main(){
	cin>>m;
    cin>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=w[i];j--){ 
			if(dp[j]<dp[j-w[i]]+w[i]){
				dp[j]=dp[j-w[i]]+w[i];
			}
		}
	}
	cout<<m-dp[m];
	return 0;
}