我们将使用Java和C中的动态编程来解决背包问题。
背包问题是技术面试中的常见问题。
面试官使用此问题来测试候选人在动态编程中的能力。

这也是程序员学习动态编程时必须解决的最基本的问题之一。

动态编程是一种算法技术，用于通过将最优化问题分解为更简单的子问题，并利用对整体问题的最优解取决于其子问题的最优解这一事实。

0/1背包的问题语句

给定n件物品的重量和价值，将这些物品放入容量为W的背包中，以获得背包中的最大总价值。

我们将在本教程中研究0/1背包问题。
在0/1背包中，一个项目可以整体包括在内，也可以排除在外。

问题的主要目标是在保持重量限制的同时最大化利润(价值总和)。

项目的权重和值分别取两个大小为n的数组。

例如：

令值数组为：

{ 60, 100, 120 }

权重数组为：

{ 10, 20, 10 }

重量限制为30。

然后为了获得最大值，我们将选择对象2和3。

这将使我们总计：

100 + 120 = 220 

解决背包问题

为了使用动态编程解决背包问题，我们建立了一个表格。
该表具有以下尺寸：

[n + 1][W + 1]

其中每个项目都有一行，最后一行对应于项目n。
我们的列从0到W。
最后一列的索引是W。

此矩阵的最后一个单元格具有索引：

[n][W]

填写表格后，该单元格将包含答案。

填表

在表格中填写单元格时，我们的目标是保持在等于列号的重量限制内，并使用从1到该行号的项目。

如果我们要填充单元格[i] [j]，则可以使用1到i之间的项，并且权重限制为j。

对于第i行，我们可以选择将第i项包含在集合中。
第i-1行的前一行包含可能的最大权重，不包括第ith个项。
如果通过包含第i个项目我们能够实现更高的价值，那么我们就在答案中包含第i个项目。

在代码方面，我们这样做如下：

for (i = 0; i<= n; i++) { 
          for (w = 0; w<= W; w++) { 
              if (i == 0 || w == 0) 
                  K[i][w] = 0; 
              else if (wt[i - 1]<= w) 
                  K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]); 
              else
                  K[i][w] = K[i - 1][w]; 
          } 
      } 

      return K[n][W]; 
  } 

这段代码显示了如何以自下而上的方式填充表格。

相同的算法如下：

• 将第0行和第0列的值设置为0。

• 用i-> [1，n]&w-> [1，W]遍历矩阵

• 填充单元格[i，j]：如果第i个项的权重<w，则单元格值的最大值为(val [i – 1] + K [i – 1] [w – wt [i – 1]]]，K [ i – 1] [w])

• 其他单元格值为K [i – 1] [w]

• 返回K [n] [W]

其中术语K [i – 1] [w]表示不包括第i个项目。
术语val [i – 1] + K [i – 1] [w – wt [i – 1]]表示包括第i个项目。

注意：因为数组val的起始索引为零，所以val [i-1]给出第i项的值。

用Java和C解决背包问题

完整的Java代码：

package com.theitroad;

import static java.lang.Integer.max;

class Kanpsack
{
  static int knapSack(int W, int wt[], int val[], int n)
{
  int i, w;
  int K[][] = new int[n + 1][W + 1];

  
  for (i = 0; i<= n; i++) {
      for (w = 0; w<= W; w++) {
          if (i == 0 || w == 0)
              K[i][w] = 0;
          else if (wt[i - 1]<= w)
              K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
          else
              K[i][w] = K[i - 1][w];
      }
  }

  return K[n][W];
}

 
  public static void main(String args[])
  {
      int val[] = new int[] { 60, 100, 120 };
      int wt[] = new int[] { 10, 20, 10 };;
      int W = 30;
      int n = val.length;
      System.out.println(knapSack(W, wt, val, n));
  }
}

      

C中的代码：

#include <stdio.h> 

//function to get maximum of two integers 
int max(int a, int b) 
{ 
  return (a > b) ? a : b; 
} 
 
int knapSack(int W, int wt[], int val[], int n) 
{ 
  int i, w; 
  int K[n + 1][W + 1]; 

  for (i = 0; i <= n; i++) { 
      for (w = 0; w <= W; w++) { 
          if (i == 0 || w == 0) 
              K[i][w] = 0; 
          else if (wt[i - 1] <= w) 
              K[i][w] = max( 
                  val[i - 1] + K[i - 1][w - wt[i - 1]], 
                  K[i - 1][w]); 
          else
              K[i][w] = K[i - 1][w]; 
      } 
  } 

  return K[n][W]; 
} 

int main() 
{ 
  int val[] = { 60, 100, 120 }; 
  int wt[] = { 10, 20, 10 }; 
  int W = 30; 
  int n = sizeof(val)/sizeof(val[0]); 
  printf("%d", knapSack(W, wt, val, n)); 
  return 0; 
} 

输出

220