哪个网站有律师做的案件,中国建设银行招聘网站甘肃分行,it培训机构培训多久,谷德设计网入口目录 背包问题01 背包背包不装满问题背包必须满问题 完全背包 背包问题
背包问题属于动态规划的一类题型
01 背包 背包不装满问题 背包必须满问题 #include iostream
using namespace std;
const int N 1010;
#include vector
int main()
{int n , V;int v[… 目录 背包问题01 背包背包不装满问题背包必须满问题 完全背包 背包问题
背包问题属于动态规划的一类题型
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] ;}//题目一//建表vectorvectorint dp(n1,vectorint(V1));//初始化 已自动初始化//填表for(int i 1; i n;i){for(int j 1 ;jV;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;iV;i){dp[0][i] -1;}//填表for(int i 1; i n;i){for(int j 1 ;jV;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] ;}//题目一//建表vectorvectorint dp(n1,vectorint(V1));//初始化 已自动初始化//填表for(int i 1; i n;i){for(int j 1 ;jV;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;iV;i){dp[0][i] -1;}//填表for(int i 1; i n;i){for(int j 1 ;jV;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;
}
