01背包与完全背包微妙的区别

本文主要是介绍01背包与完全背包微妙的区别，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

01背包与完全背包微妙的区别：

//完全背包
void solve1()
{memset(d, 0, sizeof(d));for(int i = 0; i < N; i++)for(int j = 0; j <= W; j++)if(j < w[i])d[i+1][j] = d[i][j];else d[i+1][j] = max(d[i][j], d[i+1][j-w[i]] + v[i]);printans();
}

//01背包
void solve3()
{memset(d, 0, sizeof(d));for(int i = 0; i < N; i++)for(int j = 0; j <= W; j++)if(j < w[i])d[i+1][j] = d[i][j];elsed[i+1][j] = max(d[i+1][j], d[i+1][j-w[i]]+v[i]);printans();
}

优化内存版的：

//完全背包-优化内存
void solve2()
{memset(d, 0, sizeof(d));for(int i = 0; i < N; i++)for(int j = w[i]; j <= W; j++)d[0][j] = max(d[0][j], d[0][j-w[i]] + v[i]);printans();
}

//01背包-优化内存
void solve4()
{memset(d, 0, sizeof(d));for(int i = 0; i < N; i++)for(int j = W; j >= w[i]; j--)d[0][j] = max(d[0][j], d[0][j-w[i]] + v[i]);printans();
}

完整代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 101, MAXW = 1001;
int d[MAXN][MAXW];
int w[MAXN], v[MAXN];
int N, W;
void printans()
{for(int i = 0; i <= N; i++){for(int j = 0; j <= W; j++)printf("%2d ", d[i][j]);printf("\n");}printf("%d\n", d[N][W]);
}
//原始版完全背包
void solve()
{memset(d, 0, sizeof(d));for(int i = 0; i < N; i++)for(int j = 0; j <= W; j++)for(int k = 0; k*w[i] <= j; k++)d[i+1][j] = max(d[i+1][j], d[i][j-k*w[i]] + k*v[i]);printans();
}
//完全背包
void solve1()
{memset(d, 0, sizeof(d));for(int i = 0; i < N; i++)for(int j = 0; j <= W; j++)if(j < w[i])d[i+1][j] = d[i][j];else d[i+1][j] = max(d[i][j], d[i+1][j-w[i]] + v[i]);printans();
}
//完全背包-优化内存
void solve2()
{memset(d, 0, sizeof(d));for(int i = 0; i < N; i++)for(int j = w[i]; j <= W; j++)		//顺序d[0][j] = max(d[0][j], d[0][j-w[i]] + v[i]);printans();
}
//01背包
void solve3()
{memset(d, 0, sizeof(d));for(int i = 0; i < N; i++)for(int j = 0; j <= W; j++)if(j < w[i])d[i+1][j] = d[i][j];elsed[i+1][j] = max(d[i+1][j], d[i+1][j-w[i]]+v[i]);printans();
}
//01背包-优化内存
void solve4()
{memset(d, 0, sizeof(d));for(int i = 0; i < N; i++)for(int j = W; j >= w[i]; j--)		//逆序d[0][j] = max(d[0][j], d[0][j-w[i]] + v[i]);printans();
}
int main()
{freopen("in.txt","r", stdin);while(scanf("%d%d", &N, &W) != EOF){for(int i = 0; i < N; i++)scanf("%d%d", &w[i], &v[i]);solve();solve1();solve2();solve3();}return 0;
}

这篇关于01背包与完全背包微妙的区别的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---