背包问题

背包问题属于动态规划的一类题型

01 背包

背包不装满问题

背包必须满问题

#include <iostream>
using namespace std;
const int N =1010;
#include <vector>
int main()
{int n , V;int v[N];int w[N];cin >> n >> V;//输入数据for(int i = 1;i<= n;i++){cin >> v[i] >> w[i] ;}//题目一//建表vector<vector<int>> dp(n+1,vector<int>(V+1));//初始化 已自动初始化//填表for(int i = 1; i<= n;i++){for(int j =1 ;j<=V;j++){dp[i][j] = dp[i-1][j];if(j-v[i]>= 0) dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]]+w[i]);}} //用表  cout << dp[n][V] <<endl;//题目二//初始化for(int i = 1;i<=V;i++){dp[0][i] = -1;}//填表for(int i = 1; i<= n;i++){for(int j =1 ;j<=V;j++){dp[i][j] = dp[i-1][j];if(j-v[i]>= 0 && dp[i-1][j-v[i]]!= -1) dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]]+w[i]);}} if(dp[n][V] == -1) cout << 0;//凑不到背包容量else cout << dp[n][V];return 0;
}

完全背包

其实01背包和完全背包的代码只需要改一点点

#include <iostream>
using namespace std;
const int N =1010;
#include <vector>
int main()
{int n , V;int v[N];int w[N];cin >> n >> V;//输入数据for(int i = 1;i<= n;i++){cin >> v[i] >> w[i] ;}//题目一//建表vector<vector<int>> dp(n+1,vector<int>(V+1));//初始化 已自动初始化//填表for(int i = 1; i<= n;i++){for(int j =1 ;j<=V;j++){dp[i][j] = dp[i-1][j];if(j-v[i]>= 0) dp[i][j] = max(dp[i][j],dp[i][j-v[i]]+w[i]);//改动}} //用表  cout << dp[n][V] <<endl;//题目二//初始化for(int i = 1;i<=V;i++){dp[0][i] = -1;}//填表for(int i = 1; i<= n;i++){for(int j =1 ;j<=V;j++){dp[i][j] = dp[i-1][j];if(j-v[i]>= 0 && dp[i][j-v[i]]!= -1) //改动i-1 为 idp[i][j] = max(dp[i][j],dp[i][j-v[i]]+w[i]);//改动i-1 为 i}} if(dp[n][V] == -1) cout << 0;//凑不到背包容量else cout << dp[n][V];return 0;
}