01背包问题[经典][动态规划]

学习要点

1. 学习01背包问题结题过程
2. 深入理解动态规划算法

题目描述

解法：动态规划

#include <bits/stdc++.h>
using namespace std;
int main()
{int n, bagweight;// bagweight代表行李箱空间 n代表物品个数cin >> n >> bagweight;vector<int> weight(n, 0); // 存储每件物品所占空间vector<int> value(n, 0);  // 存储每件物品价值for(int i = 0; i < n; ++i) {cin >> weight[i];}for(int j = 0; j < n; ++j) {cin >> value[j];}// dp[i][j]:0-i之间的物品任意存取放入背包容量为j的背包中的最大价值// dp[i][j]有两种状态：取与不取// 不取：dp[i][j] = dp[i-1][j]// 取：  dp[i][j] = dp[i-1][j-weight(i-1)]+ value[i]vector<vector<int>> dp(n,vector<int>(bagweight +1,0));for(int i = 0; i<=bagweight;i++){if(i >= weight[0]){dp[0][i] = value[0];// cout << dp[0][i] << endl;}}for(int i = 1; i< n; i++){for(int j = 1; j<= bagweight;j++){if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 如果装不下这个物品,那么就继承dp[i - 1][j]的值else {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}}cout << dp[n-1][bagweight] << endl;return 0;
}