网站备案去哪里办理_dw个人网站设计模板免费_东莞seo排名公司_山东进一步优化

题目：46. 携带研究材料（第六期模拟笔试）

思路:经典01背包问题

一定要记住初始化的方法和弄清楚对应的下标关系

代码:

#include<bits/stdc++.h>
using namespace std;int main(){int m;int n;cin>>m>>n;vector<int>weight(m,0) ;vector<int>value(m,0) ;//定义dp数组for(int i = 0;i < m;i++)cin>>weight[i];for(int i = 0;i < m;i++)cin>>value[i];vector<vector<int>>dp(m , vector<int>(n+1,0));for(int i = weight[0]; i<=n ;i++){dp[0][i] = value[0];}for(int i = 1;i< m ;i++)for(int j = 1;j<=n;j++){if( j < weight[i])dp[i][j] = dp[i-1][j];elsedp[i][j] = max(dp[i-1][j] ,dp[i-1][j - weight[i]]+value[i]);}cout <<dp[m-1][n];return 0 ;
}