网站改版 价格,linux做网站网络课堂,网站的建设包括以下几个阶段,已有网站 需要整改 怎么做题目#xff1a;
题解#xff1a;
本题是非常经典的dp问题#xff0c;但是如果你是dp入门者dp小白我不建议直接一上来就学习01背包问题#xff0c;我的建议是先学习leetcode动态规划#xff08;基础版#xff09;从头开始慢慢领悟这个路线更适合理解动态规划的本质。
…题目
题解
本题是非常经典的dp问题但是如果你是dp入门者dp小白我不建议直接一上来就学习01背包问题我的建议是先学习leetcode动态规划基础版从头开始慢慢领悟这个路线更适合理解动态规划的本质。
小局部最优的策略是选不选最后一个物品使小局部的价值最大。
dp[i][j]代表选了i种物品重量为j的状态。
#include iostream
using namespace std;
int main(){int w[1005]{0},v[1005]{0};int total,N;cintotalN;for(int i1;iN;i)cinw[i]v[i];int dp[1005][1005]{0};for(int i1;iN;i){for(int j1;jtotal;j){dp[i][j]dp[i-1][j];if(jw[i])dp[i][j]max(dp[i][j],dp[i-1][j-w[i]]v[i]);}}coutdp[N][total];return 0;
}
