#include <iostream> using namespace std; int a[100010],dp[100010]; int main() { int v,n;cin>>v>>n; for(int i = 1;i<=n;i++){ cin>>a[i]; } for(int i = 1;i<=n;i++){ for(int j = v;j>=0;j--){ if(j>=a[i]){ dp[j] = max(dp[j],dp[j-a[i]]+a[i]); } } } cout<<v-dp[v]; return 0; } // 64 位输出请用 printf("%lld")
状态转移方程为当剩余空间可以装当前物品时,dp[i] = max(dp[i],dp[i-a[i]]+a[i])选第i个和不选第i个。