背包+回溯
1.第一种方法没有优化
2.第二种方法是空间优化的
#include<iostream> #include<algorithm> using namespace std; struct goods{ int v; int w; }g[20]; bool big(goods a,goods b){ return a.v>b.v; } int flag[20]; int dp[20][100]; int main(){ int m,n; while(cin>>m>>n){ for(int i=1;i<=n;i++){ cin>>g[i].v; g[i].w=g[i].v; } sort(g+1,g+n+1,big); for(int i=0;i<=n;i++){ for(int j=0;j<=m;j++){ if(i==0||j==0){ dp[i][j]=0;continue; }else{ if(j>=g[i].w){ dp[i][j]=max(dp[i-1][j],dp[i-1][j-g[i].w]+g[i].v); }else{ dp[i][j]=dp[i-1][j]; } } } } int p=dp[n][m]; if(p<m)cout<<0<<endl; else{ int sum=0; int i=n; int j=m; while(p){ if(p!=dp[i-1][m]){ sum++; p-=g[i].v; m-=g[i].w; } i--; }cout<<sum<<endl; } } return 0; }
2.
#include<iostream> #include<climits> using namespace std; //保证在包装满的情况下,拿最少的物品 const int maxn=101; int w[maxn];//硬币的面值就是硬币的重量 //每个硬币的价值都看作1,找价值最小的 int dp[maxn]; int main(){ int m,n; while(cin>>m>>n){ for(int i=0;i<n;i++){ cin>>w[i]; } for(int i=0;i<=m;i++)dp[i]=100000; dp[0]=0; for(int i=0;i<n;i++){ for(int j=m;j>=0;j--){ if(j>=w[i]){ dp[j]=min(dp[j],dp[j-w[i]]+1); } } } if(dp[m]==100000){ cout<<0<<endl; }else{ cout<<dp[m]<<endl; } } return 0; }