这题一眼就能看出是01背包问题，但是跟模板不太一样：每个物品只有重量，没有价值，而且求的是背包剩余的最小容量。但你仔细思考也会发现这个问题与01背包模板题是可以转化的。既然每个物品没有价值，那么就把它们的价值定义为它们的重量，求剩余最小容量的问题就变成了求剩余最少价值。然后你会发现，用总价值减去装了的价值，就是问题的答案。总价值是什么？是背包的容量V，也就是背包装的价值上限。 所以，我们只要把这道题当作01背包模板题做就行了。 注意：把所有代表价值的数组全部换成代表重量的数组，最后的答案应该是V-dp[n][V]，也就是背包容量减去最大能装的重量就是剩余最小重量。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ AC代码（如果你看懂了，你应该不会抄） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

man!what can I say!AC O!U!T! #include<bits/stdc++.h> using namespace std; int v,m; int c[31]; int dp[31][20005]; int main(){ cin>>v>>m; for(int i=1;i<=m;i++){ cin>>c[i]; } for(int i=1;i<=m;i++){ for(int j=1;j<=v;j++){ dp[i][j] = dp[i-1][j]; if(j>=c[i]) dp[i][j] = max( dp[i-1][j] , dp[i-1][j-c[i]]+c[i]); } } cout<<v-dp[m][v]; return 0; }

#include<bits/stdc++.h> using namespace std; int dp[35][20005]; int a[35]; int main(){ int rl,wp; cin>>rl>>wp; } 半小时

也还好，不算很难

#include<bits/stdc++.h> using namespace std; int v,n; int c[31]; int dp[31][20005]; int main(){ cin >> v >> n; for(int i = 1;i <= n;i ++){ cin >> c[i]; } for(int i = 1;i <= n;i ++){ for(int j = 1;j <= v;j ++){ dp[i][j] = dp[i-1][j]; if(j >= c[i]) dp[i][j] = max(dp[i-1][j] , dp[i-1][j-c[i]] +c[i]); } } cout << v - dp[n][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(inlinet 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; }

#include<cstdio> using namespace std; int m,n; int f[20010]; int w[40]; int main(){ int i,j; scanf("%d%d",&m,&n); for(i=1;i<=n;i++){ scanf("%d",&w[i]); } for(i=1;i<=n;i++){ for(j=m;j>=w[i];j--){ if(f[j]<f[j-w[i]]+w[i]){ f[j]=f[j-w[i]]+w[i]; } } } printf("%d\n",m-f[m]); }