因为之前做过实验，这里就不赘述了。

背包类&初始化数据：

#include<vector>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

#define N   10

class Backage
{
private:
    int         num;
    int         w[N] = {19,23,12,34,24,34,56,24,53,35};
    int         v[N] ={57,68,87,17,12,21,31,42,14,15};
    int         capility;
    int         cv;
    int         cw;
    int         bestv;
public:
    Backage();
    int Backtrace(int i);
    int Dp();
};

1.回溯法

Backage::Backage(){
    num=10;
    capility=300;
    cv=0;
    cw=0;
    bestv=0;
}

int Backage::Backtrace(int i)
{
    if (i>=N){
        bestv=bestv>cv?bestv:cv;
        return bestv;
    }
    if (cw+w[i]>capility)
        return bestv;
    int sum=0;
    for(int j=i;j<N;j++)
        sum+=v[j];
    sum+=cv;
    if (sum<bestv){
        return bestv;
    }
    cv+=v[i];
    cw+=w[i];
    Backtrace(i+1);
    cv-=v[i];
    cw-=w[i];
    Backtrace(i+1);
    return bestv;
}

int main(){
    Backage b;
    int bestv1=b.Backtrace(0);
    cout<<"回溯法求得最大价值为："<<bestv1<<endl;
    system("pause");
    return 1;
}

2.动态规划法

int Backage::Dp()
{
    int DP[capility]={0};
    for(int j=0;j<N;j++)
    {
        for (int i=capility;i>=w[j];i--)
        {
            DP[i]=DP[i]>(DP[i-w[j]]+v[j])?DP[i]:(DP[i-w[j]]+v[j]);
        }
    }
    return DP[capility];
}


int main(){
    Backage b;
    int bestv2=b.Dp();
    cout<<"动态规划法求得最大价值为："<<bestv2<<endl;
    system("pause");
    return 1;
}