描述
有N种物品和一个容积为M的背包。第i种物品的体积w[i]，价值是d[i]。求解将哪些物品装入背包可使价值总和最大。(N<=100,M <= 600)。一种物品可以拿任意多个

求能拿取的最大总价值

输入
第一行是两个整数, N 和 M
第二行是N种物品的体积
第三行是N种物品的价值
输出
输出：
能获得的最大价值
样例输入
3 7
3 3 6
10 20 30
样例输出
40

#include ‘iostream’
#include ‘vector’
#include ‘algorithm’//’‘代表<>
using namespace std;
int main() {
int N, M;
cin >> N >> M;

vector<int> w(N); // 物品的体积
vector<int> d(N); // 物品的价值

for (int i = 0; i < N; ++i) {
    cin >> w[i];
}

for (int i = 0; i < N; ++i) {
    cin >> d[i];
}
vector<int> dp(M + 1, 0); 
//创建了一个大小为 M+1 的整数向量 dp，并初始化全部为 0
//dp[i]表示容量为i的背包所能获得的最大价值
for (int i = 0; i < N; ++i) {
    for (int j = w[i]; j <= M; ++j) {
        dp[j] = max(dp[j], dp[j - w[i]] + d[i]);
//将当前物品放入后剩余容量所能获得的最大价值与当前最大价值进行比较
    }
}
cout << dp[M] << endl;
return 0;

}