网站建设在线建站,国际军事新闻视频,遵义市住房和城乡建设局官方网站,深圳营销型网站建设电话题目#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;
}
