0/1背包+回溯

背包+回溯
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;
}