方法一背包：此题背包的体积和价值是同一个东西 此题虽然不卡剪枝，但是这里还是用了一下剪枝
#include<iostream> #include<algorithm> using namespace std; int dp[30005],v,n,k; int main(){ cin>>v>>n; for(int i=1;i<=n;i++){ cin>>k; for(int j=v;j>=k;j--){ dp[j]=max(dp[j],dp[j-k]+k); if(dp[j]==v){//当已经找到了等于背包大小的重量直接输出（剪枝） cout<<0<<endl; return 0; } } } cout<<v-dp[v]<<endl; return 0; }方法二搜索：直接用搜索也可以做，分为选择和不选择两种状态，最后取箱子重量和最大值即可
#include<iostream> #include<string> #include<algorithm> using namespace std; int v,n,w[20005],ans=0; void dfs(int k,int sum){ if(sum==v){//剪枝，一旦箱子可以装满，直接输出，退出程序 cout<<0; exit(0); } if(sum>v){// return; } if(k>n){//当k>n是搜索完了，进行比较取值就可以了（此处sum一定小于v） ans=max(sum,ans); return; } dfs(k+1,sum);//不选择第k个物品 dfs(k+1,sum+w[k]);//选择第k个物品 } int main(){ cin>>v>>n; for(int i=0;i<n;i++){ cin>>w[i]; } dfs(0,0); cout<<v-ans; return 0; }