数据结构和算法

DSA - 主页 DSA - 概述 DSA - 环境设置 DSA - 算法基础 DSA - 渐近分析

数据结构

DSA - 数据结构基础 DSA - 数据结构和类型 DSA - 数组数据结构

链接列表

DSA - 链接列表数据结构 DSA - 双向链接列表数据结构 DSA - 循环链表数据结构

堆栈 &队列

DSA - 堆栈数据结构 DSA - 表达式解析 DSA - 队列数据结构

搜索算法

DSA - 搜索算法 DSA - 线性搜索算法 DSA - 二分搜索算法 DSA - 插值搜索 DSA - 跳跃搜索算法 DSA - 指数搜索 DSA - 斐波那契搜索 DSA - 子列表搜索 DSA - 哈希表

排序算法

DSA - 排序算法 DSA - 冒泡排序算法 DSA - 插入排序算法 DSA - 选择排序算法 DSA - 归并排序算法 DSA - 希尔排序算法 DSA - 堆排序 DSA - 桶排序算法 DSA - 计数排序算法 DSA - 基数排序算法 DSA - 快速排序算法

图形数据结构

DSA - 图形数据结构 DSA - 深度优先遍历 DSA - 广度优先遍历 DSA - 生成树

树数据结构

DSA - 树数据结构 DSA - 树遍历 DSA - 二叉搜索树 DSA - AVL 树 DSA - 红黑树 DSA - B树 DSA - B+ 树 DSA - 伸展树 DSA - 尝试 DSA - 堆数据结构

递归

DSA - 递归算法 DSA - 使用递归的汉诺塔 DSA - 使用递归的斐波那契数列

分而治之

DSA - 分而治之 DSA - 最大最小问题 DSA - 施特拉森矩阵乘法 DSA - Karatsuba 算法

贪婪算法

DSA - 贪婪算法 DSA - 旅行商问题(贪婪方法) DSA - Prim 最小生成树 DSA - Kruskal 最小生成树 DSA - Dijkstra 最短路径算法 DSA - 地图着色算法 DSA - 分数背包问题 DSA - 作业排序截止日期 DSA - 最佳合并模式算法

动态规划

DSA - 动态规划 DSA - 矩阵链乘法 DSA - Floyd Warshall 算法 DSA - 0-1 背包问题 DSA - 最长公共子序列算法 DSA - 旅行商问题(动态方法)

近似算法

DSA - 近似算法 DSA - 顶点覆盖算法 DSA - 集合覆盖问题 DSA - 旅行商问题(近似方法)

随机算法

DSA - 随机算法 DSA - 随机快速排序算法 DSA - Karger 最小割算法 DSA - Fisher-Yates 洗牌算法

DSA 有用资源

DSA - 问答 DSA - 快速指南 DSA - 有用资源 DSA - 讨论


0-1 Knapsack Problem



We discussed the fractional knapsack problem using the greedy approach, earlier in this tutorial. It is shown that Greedy approach gives an optimal solution for Fractional Knapsack. However, this chapter will cover 0-1 Knapsack problem using dynamic programming approach and its analysis.

Unlike in fractional knapsack, the items are always stored fully without using the fractional part of them. Its either the item is added to the knapsack or not. That is why, this method is known as the 0-1 Knapsack problem.

Hence, in case of 0-1 Knapsack, the value of xi can be either 0 or 1, where other constraints remain the same.

0-1 Knapsack cannot be solved by Greedy approach. Greedy approach does not ensure an optimal solution in this method. In many instances, Greedy approach may give an optimal solution.

0-1 Knapsack Algorithm

Problem Statement − A thief is robbing a store and can carry a maximal weight of W into his knapsack. There are n items and weight of ith item is wi and the profit of selecting this item is pi. What items should the thief take?

Let i be the highest-numbered item in an optimal solution S for W dollars. Then S’ = S − {i} is an optimal solution for W – wi dollars and the value to the solution S is Vi plus the value of the sub-problem.

We can express this fact in the following formula: define c[i, w] to be the solution for items 1,2, … , i and the maximum weight w.

The algorithm takes the following inputs

  • The maximum weight W

  • The number of items n

  • The two sequences v = <v1, v2, …, vn> and w = <w1, w2, …, wn>

The set of items to take can be deduced from the table, starting at c[n, w] and tracing backwards where the optimal values came from.

If c[i, w] = c[i-1, w], then item i is not part of the solution, and we continue tracing with c[i-1, w]. Otherwise, item i is part of the solution, and we continue tracing with c [i-1, w-W].

Dynamic-0-1-knapsack (v, w, n, W)
for w = 0 to W do
   c[0, w] = 0
for i = 1 to n do
   c[i, 0] = 0
   for w = 1 to W do
      if wi ≤ w then
         if vi + c[i-1, w-wi] then
            c[i, w] = vi + c[i-1, w-wi]
         else c[i, w] = c[i-1, w]
      else
         c[i, w] = c[i-1, w]

The following examples will establish our statement.

Example

Let us consider that the capacity of the knapsack is W = 8 and the items are as shown in the following table.

Item A B C D
Profit 2 4 7 10
Weight 1 3 5 7

Solution

Using the greedy approach of 0-1 knapsack, the weight that’s stored in the knapsack would be A+B = 4 with the maximum profit 2 + 4 = 6. But, that solution would not be the optimal solution.

Therefore, dynamic programming must be adopted to solve 0-1 knapsack problems.

Step 1

Construct an adjacency table with maximum weight of knapsack as rows and items with respective weights and profits as columns.

Values to be stored in the table are cumulative profits of the items whose weights do not exceed the maximum weight of the knapsack (designated values of each row)

So we add zeroes to the 0th row and 0th column because if the weight of item is 0, then it weighs nothing; if the maximum weight of knapsack is 0, then no item can be added into the knapsack.

0-1_knapsack_problems

The remaining values are filled with the maximum profit achievable with respect to the items and weight per column that can be stored in the knapsack.

The formula to store the profit values is −

$$c\left [ i,w ight ]=max\left\{c\left [ i-1,w-w\left [ i ight ] ight ]+P\left [ i ight ] ight\}$$

By computing all the values using the formula, the table obtained would be −

maximum_weight

To find the items to be added in the knapsack, recognize the maximum profit from the table and identify the items that make up the profit, in this example, its {1, 7}.

maximum_profit_12

The optimal solution is {1, 7} with the maximum profit is 12.

Analysis

This algorithm takes Ɵ(n.w) times as table c has (n+1).(w+1) entries, where each entry requires Ɵ(1) time to compute.

Implementation

Following is the final implementation of 0-1 Knapsack Algorithm using Dynamic Programming Approach.

#include <stdio.h>
#include <string.h>
int findMax(int n1, int n2){
   if(n1>n2) {
      return n1;
   } else {
      return n2;
   }
}
int knapsack(int W, int wt[], int val[], int n){
   int K[n+1][W+1];
   for(int i = 0; i<=n; i++) {
      for(int w = 0; w<=W; w++) {
         if(i == 0 || w == 0) {
            K[i][w] = 0;
         } else if(wt[i-1] <= w) {
            K[i][w] = findMax(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[5] = {70, 20, 50};
   int wt[5] = {11, 12, 13};
   int W = 30;
   int len = sizeof val / sizeof val[0];
   printf("Maximum Profit achieved with this knapsack: %d", knapsack(W, wt, val, len));
}

Output

Maximum Profit achieved with this knapsack: 120
#include <bits/stdc++.h>
using namespace std;
int max(int a, int b){
   return (a > b) ? a : b;
}
int knapSack(int W, int wt[], int val[], int n){
   int i, w;
   vector<vector<int>> K(n + 1, vector<int>(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[] = { 70, 20, 50 };
   int wt[] = { 11, 12, 13 };
   int W = 30;
   int n = sizeof(val) / sizeof(val[0]);
   cout << "Maximum Profit achieved with this knapsack: " << knapSack(W, wt, val, n);
   return 0;
}

Output

Maximum Profit achieved with this knapsack: 120
import java.util.*;
import java.lang.*;
public class Knapsack {
   public static int findMax(int n1, int n2) {
      if(n1>n2) {
         return n1;
      } else {
         return n2;
      }
   }
   public static int knapsack(int W, int wt[], int val[], int n) {
      int K[][] = new int[n+1][W+1];
      for(int i = 0; i<=n; i++) {
         for(int w = 0; w<=W; w++) {
            if(i == 0 || w == 0) {
               K[i][w] = 0;
            } else if(wt[i-1] <= w) {
               K[i][w] = findMax(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 = {70, 20, 50};
      int[] wt = {11, 12, 13};
      int W = 30;
      int len = val.length;
      System.out.print("Maximum Profit achieved with this knapsack: " + knapsack(W, wt, val, len));
   }
}

Output

Maximum Profit achieved with this knapsack: 120
def knapsack(W, wt, val, n):
   K = [[0] * (W+1) for i in range (n+1)]
   for i in range(n+1):
      for w in range(W+1):
         if(i == 0 or w == 0):
            K[i][w] = 0
         elif(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]

val = [70, 20, 50];
wt = [11, 12, 13];
W = 30;
ln = len(val);
profit = knapsack(W, wt, val, ln)
print("Maximum Profit achieved with this knapsack: ")
print(profit)

Output

Maximum Profit achieved with this knapsack: 
120