【动态规划】0-1背包问题（滚动数组篇）

简单的0-1背包问题滚动数组

原理

所谓滚动数组其实就是把二维dp数组换成了一维dp数组
因为关键的步骤

dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])

只要把第i-1行的数据及时赋给第i行，就可以少一维数据
也就是：

dp[j]=max(dp[j],dp[j-weight[i]]+value[i])

代码

#include <bits/stdc++.h>
using namespace std;int main() {int n,vol;int j,k;cin>>n;cin>>vol;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];}vector<int> dp(vol+1);//初始化dp[0]dp[0]=0;for(int i=0;i<n;i++){for(j=vol;j>=weight[i];j--){dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);}}cout<<dp[vol];return 0;
}