这道题看似是搜索，但是可以用背包做。 题目要求求出最小的剩余空间，也就是要求出最大的可装重量 这样，我们可以将一个物体的重量当作它的价值，进而将题目转变为一个基本的 010101 背包问题： 有一个箱子容量为 VVV （正整数， 000 ＜＝ VVV ＜＝ 200002000020000 ），同时有 nnn 个物品（ 000 ＜ nnn ＜＝ 303030 ），每个物品有一 个体积（正整数）和一个价值（等于体积）。 要求 nnn 个物品中，任取若干个装入箱内，使总价值最大。 对于每一个物体，都有两种状态：装 与不装 那么，对于任意重量 mmm 的最大价值 fff ( mmm ) === maxmaxmax ( fff ( mmm −-− www [ iii ] ) +++ www [ iii ], fff ( mmm ) )（ www 为重量（即价值）） 其中， fff ( mmm −-− www [ iii ] ) 指在装了物品 iii 后，箱子的剩余容量能装的最大重量 fff ( mmm −-− www [ iii ] ) +++ www [ iii ] 指在在装了物品 iii 后，箱子能装的最大重量

洛谷里这个没有re的

#include<bits/stdc++.h> using namespace std; int n,m,w; int dp[20005]={0}; int main(){ scanf("%d%d",&m,&n); for(int i=1;i<=n;i++){ scanf("%d",&w); for(int j=m;j>=w;j--){ if(j>=w){ dp[j]=max(dp[j],w+dp[j-w]); } } } printf("%d",m-dp[m]); return 0; }

逝十分简单的一道01背包的题 欢迎加入团队

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

#include<bits/stdc++.h> using namespace std; const int V=2e4+10; int main(){ int v,n,dp[35][V]={}; int w[105]={}; cin>>v>>n; for(int i=1;i<=n;i++) cin>>w[i]; for(int i=1;i<=n;i++){ for(int j=1;j<=v;j++){ if(j>=w[i]){ dp[i][j]=max(dp[i-1][j],w[i]+dp[i-1][j-w[i]]); }else{ dp[i][j]=dp[i-1][j]; } } } cout<<v-dp[n][v]; return 0; }