算法--0/1背包问题

目录

0/1背包问题：

思路分析

---

0/1背包问题：

The 0-1 knapsack problem is a well-known optimization challenge in computer science. Suppose we have a collection of n distinct items along with a backpack that has a limited carrying capacity. Each item i has an associated weight w_i and value v_i. Our goal is to determine the optimal subset of items to include in the backpack such that the total value is maximized without exceeding the backpack's capacity constraints.

0/1背包，即物体只能整个放入或者整个不放入。

对于背包问题，你先解决小背包（子背包）问题，再逐步解决原来的问题。

思路分析

确定状态转移

在解决0/1背包问题时，在确定选哪几件物品的时候首先要满足的就是：当某一件特定物体（即第i个）的质量超过了所剩的空间时，则无法将其装入

为了解决好0/1背包问题，在选择哪些东西装进包里这一步骤上必须要做到的就是：先确保当前正在考虑的那个物体（即第i号）的质量没有超过包里剩下的空间

如果放入物品的话，则需要权衡是否将其放入？也就是说，在"放入"与"不放入"两个维度上确定背包的最大价值。

（c++语言实现）代码如下：

#include

using namespace std;

#define C 10

int V[6][11];

int x[5];

int KnapSack(int n, int w[], int v[]);

int max(int x, int y);

void printV();

int main()

{

int w[] = { 2, 2, 6, 5, 4 };

int v[] = { 6, 3, 5, 4, 6 };

cout << "背包的最大价值为:" << KnapSack(5, w, v) << endl;

cout << "装入背包的物品是:";

for (int i = 0; i < 5; i++)

{

if (x[i]==1)

{

cout << "物品" << i + 1<<",";

}

}

printf("\n");

printf("输出背包列表为：\n");

printV();

cout << endl;

return 0;

}

int max(int x, int y){

if (x>y)

{

return x;

}

else

{

return y;

}

}

int KnapSack(int n, int w[], int v[]){

int i, j;

//1.初始化第0列

for ( i = 0; i <=n; i++)

{

V[i][0] = 0;

}

//2.初始化第0行

for ( j = 0; j <=C; j++)

{

V[0][j] = 0;

}

//3.初始化第i行，进行i次迭代

for (i = 1; i <=n; i++)

{

for ( j = 1; j <= C; j++)

{

if (j<w[i-1])

{

//第j个物品重量大加不进去

V[i][j] = V[i - 1][j];

}

else

{

V[i][j] = max(V[i - 1][j], V[i-1][j-w[i-1]]+v[i-1]);

}

}

}

//4.求装入的物品

for ( j = C,i=n; i>0; i--)

{

if (V[i][j]>V[i-1][j])

{

x[i-1] = 1;

j = j - w[i-1];

}

else

{

x[i-1] = 0;

}

}

//5.返回背包的最大价值

return V[n][C];

}

void printV(){

for (int i = 0; i < 6; i++)

{

for (int j = 0; j < C+1; j++)

{

if (j==0)

{

printf("%d\t", i);

}

else

{

printf("%d\t", V[i][j]);

}

}

printf("\n");

}

}