讲透完全背包算法 - Unbounded knapsack problem


讲透完全背包算法 - Unbounded knapsack problem
已知:有一个容量为V的背包和N件物品,第i件物品的重量是weight[i],收益是cost[i]。
条件:每种物品都有无限件,能放多少就放多少。
问题:在不超过背包容量的情况下,最多能获得多少价值或收益


基于01背包的分析,由于不必考虑物品的重复放入,故v的循环采用顺序即可。代码如下:
    for(i = 0; i < N; ++i)
    {
        for(j = weight[i]; j <= V; ++j)  /* j<weight[i]的对前面的状态不会有影响 */
        {
            int tmp = maxV[j-weight[i]]+value[i];
            maxV[j] = (maxV[j] > tmp) ? maxV[j] : tmp;
        }
    }
http://ufownl.blog.163.com/blog/static/1250122200933113914579
s[i][j]=max{s[i-1][j], s[i][j-v[i]]+w[i]}
for (int i=0; i<=V; i++) s[0][i]=0;  // 边界
for (int i=1; i<=N; i++)
{
      for (int j=0; j<=V; j++)
      {
            int t=0;
            if (j-v[i]>=0) t=s[i][j-v[i]]+w[i];
            s[i][j]=max(s[i-1][j], t);
      }
}
将状态记录数组改成一维可以将空间复杂度降为O(V)
for (int i=1; i<=N; i++)
{
      for (int j=v[i]; j<=V; j++) s[j]=max(s[j], s[j-v[i]]+w[i]);
}
https://github.com/PetarV-/Algorithms/blob/master/Dynamic%20Programming/Unbounded%20Knapsack.cpp


0/1背包和完全背包的java解法
public static int unpack(int[] values, int[] weights, int maxWeight) {
  int[] ans = new int[maxWeight + 1];
  for (int i = 0; i < values.length; i++) {
    for (int j = weights[i]; j <= maxWeight; j++) {
      int takeValue = values[i] + ans[j - weights[i]];
      if (takeValue > ans[j]) {
        ans[j] = takeValue;
      }
    }
  }
  return ans[maxWeight];
}
基本思路(直接扩展01背包的方程)
由于本问题类似于01背包问题,在01背包问题中,物品要么取,要么不取,而在完全背包中,物品可以取0件、取1件、取2件...直到背包放不下位置。因此,可以直接在01背包的递推式中扩展得到。
  1. f[i][v]:表示前i件物品放入容量为v的容量中时的最大收益  
  2. 递推式:  
  3. f[i][v] = max(f[i - 1][v],f[i - K * weight[i]] + K * Value[i]); 其中  1 <= K * weight[i] <= v,(v指此时背包容量) 
程序需要求解N*V个状态,每一个状态需要的时间为O(v/Weight[i]),总的复杂度为O(NV*Σ(V/c[i]))。
  1. int Completeknapsack()  
  2. {  
  3.     //边界条件  
  4.     for (int i = 0;i <= N;i++)  
  5.     {  
  6.         f[i][0] = 0;  
  7.     }  
  8.     for (int v = 0;v <= V;v++)  
  9.     {  
  10.         f[0][v] = 0;  
  11.     }  
  12.     //递推  
  13.     for (int i = 1;i <= N;i++)  
  14.     {  
  15.         for (int v = 1;v <= V;v++)  
  16.         {  
  17.             f[i][v] = 0;  
  18.             int nCount = v / weight[i];  
  19.             for (int k = 0;k <= nCount;k++)  
  20.             {  
  21.                 f[i][v] = max(f[i][v],f[i - 1][v - k * weight[i]] + k * Value[i]);  
  22.             }  
  23.         }  
  24.     }  
  25.     return f[N][V];  
3、转换为01背包问题求解(直接利用01背包)
思路 1、完全背包的物品可以取无限件,根据背包的总容量V和第i件物品的总重量Weight[i],可知,背包中最多装入V/Weight[i](向下取整)件该物品。因此可以直接改变第i件物品的总个数,使之达到V/Weight[i](向下取整)件,之后直接利用01背包的思路进行操作即可。
举例:物品个数N = 3,背包容量为V = 5。
拆分之前的物品序列:
拆分之后的物品序列:



若两件物品i、j满足c[i]<=c[j]且w[i]> =w[j],则将物品j去掉,不用考虑。这个优化的正确性显然:任何情况下都可将价值小费用高得j换成物美价廉的i,得到至少不会更差的方案。

第i种物品拆成费用为c[i]*2^k、价值为w[i]*2^k的若干件物品,其中k满足c[i]*2^k<=V。这是二进制的思想,因为不管最优策略选几件第i种物品,总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log V/c[i])件物品

http://www.ahathinking.com/archives/108.html
这种实现方式是对完全背包的基本实现做了一个优化,叫“二进制拆分”。所谓“拆分物体”就是将一种无限件物品拆分成有效的几件物品,拆分物体的目的是通过减少物品个数来降低复杂度。
在完全背包中,每种物品i对于容量v来讲实际上相当于有v/c[i]件,故在上述的基本实现中,k就要循环测试v/c[i]次。
这里的拆分是利用了一种二进制思想:即任何数字都可以表示成若干个2^k数字的和,例如7可以用1+2+2^2表示;这很好理解,因为任何正数都可以转成二进制,二进制就是若干个“1”(2的幂数)之和。
所以不管最优策略选择几件物品i,我们都可以将物品i拆成费用为c[i]*2^k,价值为w[i]*2^k的若干件物品。这样物品的状态数就降为了log(v/c[i]),是很大的改进。

 * 状态转移方程:f(i,v) = max{ f(i-1,v-2^k*c[i]) + 2^k*w[i] | 0<=k<=log v/c[i]  }
 * 每件物品降低为 log(v/c[i]) 种状态
 */
for(k = 1; k <= j/weight[i]; k <<= 1)
{
     if(maxV[i-1][j-k*weight[i]] + k*value[i] > max_tmp)
     {
          max_tmp = maxV[i-1][j-k*weight[i]] + k*value[i];
     }
}


完全背包中的逆向思维
我们知道,在01背包和完全背包的实现中,都是针对每种物品进行讨论,即外循环都是for i=0…n,然后每种物品对于容量v的变化而求得最大价值;
在完全背包中,由于物品的件数无限,所以我们可以倒过来想,我们针对每个容量讨论,外循环为容量,对于每个容量j,我们求j对于所有物品能装载的最大价值,这样一来我们就能将时间复杂度降为O(N*V)了。
    for(i = 1; i <= V; ++i)
    {
        int i_maxV = 0;        /* 记录子问题i的最优解 */
        /* 每个容量求面对所有物体能装载的最大价值 */
        for(j = 0; j < N; ++j)
        {
            if(i >= weight[j])
            {
                int tmp = maxV[i-weight[j]] + value[j];
                maxValue[i][j] = maxV[i-1] > tmp ? maxV[i-1] : tmp;
            }else
            {
                maxValue[i][j] = maxV[i-1];
            }
            if(maxValue[i][j] > i_maxV)
            {
                i_maxV = maxValue[i][j];
            }
        }
        maxV[i] = i_maxV;
    }
http://sighingnow.github.io/algorithm/coin.html
仅有 n 种指定面值的硬币(c1, c2, c3, ..., cn), 将钱 N 兑换成 这些面值的硬币,总共有多少种兑换方法?
最简单的递推的想法: 枚举每种货币的使用次数,当使用 k 次第 n 种硬币凑出了 j 钱数的方案,应当等于只使用了前 n-1 种硬币凑出了 dp[j-k*coin[n]] 钱数,而凑出钱数 money 的总方案,应当等于仅使用了 前 1 中硬币、仅使用的前 2 种硬币、...、仅使用了前 n-1 中硬币、使用了全部n种硬币的方案的总和。暗按照这个想法,直接递推求解即可。
int dp[MAX_N] = {0};

int exchange(int money, int n, int coin[]) {
    dp[0] = 1;
    for(int i = 1; i <= n; ++i) {
        for(int j = money; j >= coin[i]; --j) {
            for(int k = j / coin[i]; k > 0; --k) {
                dp[j] += dp[j - k*coin[i]];
            }
        }
    }
    return dp[money];
}
这个方法还可以进一步简化。在上面的方法中,我们从大往小地枚举钱数,考虑到每种硬币都有无限枚可以选,因此,在选择第 i 中硬币时,我们只需要从一个绝无已经选择第 i 种硬币的可能的情形 开始枚举递推即可。在具体实现上,只要改变总钱数 j 的递推顺序即可。进一步地,采用压缩空间的写法,代码如下:
int dp[MAX_N] = {0};

int exchange(int money, int n, int coin[])
{
    dp[0] = 1;
    for(int i = 1; i <= n; ++i) {
        for(int j = coin[i]; j <= money; ++j) {
            dp[j] += dp[j-coin[i]];
        }
    }
    return dp[money];
}
这种方法与求解完全背包的算法的思路有很大的相似之处。

母函数

钱币兑换问题本质上是一个组合问题:以 n 中硬币来组合出制定的钱数。因此,也可以通过母函数的方法来求解钱币组合问题。
f(n) = (1+x+x^(c1)+x^(2*c1)+...) * (1+x+x^(c2)+x^(2*c2)+...) * (1+x+x^(c3)+x^(2*c2)+...) * ... * (1+x+x^(cn)+x^(2*cm)+...)
所要求的兑换方案数,即第 n 项的系数,接下来,模拟多项式展开即可。
https://mytwocentsads.wordpress.com/2012/09/01/knapsack-problem-a-java-implementation/
Read full article from 讲透完全背包算法 - Unbounded knapsack problem

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts