刷代码随想录有感(110):动态规划——完全背包问题
题干:
代码:
#include<bits/stdc++.h>
using namespace std;
int n, bagweight;
void solve(){vector<int>dp(bagweight + 1, 0);vector<int>weight(n, 0);vector<int>value(n, 0);for(int i = 0; i < n; i++){cin>>weight[i]>>value[i];}for(int i = 0; i < n; i++){for(int j = weight[i]; j <= bagweight; j++){dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}cout<<dp[bagweight]<<endl;
}int main(){while(cin>>n>>bagweight){solve();}
}
完全背包问题与01背包的最大区别就是01背包只能装一次,完全背包可以装多次。
最大的不同就是遍历背包时,是从前向后遍历的。