Knapsack - Unbounded 完全背包


http://love-oriented.com/pack/P02.html
有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
这个问题非常类似于01背包问题,所不同的是每种物品有无限件。也就是从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路,令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程,像这样:
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
这跟01背包问题一样有O(VN)个状态需要求解,但求解每个状态的时间已经不是常数了,求解状态f[i][v]的时间是O(v/c[i]),总的复杂度可以认为是O(V*Σ(V/c[i])),是比较大的。

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}


一个简单有效的优化
完全背包问题有一个很简单有效的优化,是这样的:若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j],则将物品j去掉,不用考虑。这个优化的正确性显然:任何情况下都可将价值小费用高得j换成物美价廉的i,得到至少不会更差的方案。对于随机生成的数据,这个方法往往会大大减少物品的件数,从而加快速度。然而这个并不能改善最坏情况的复杂度,因为有可能特别设计的数据可以一件物品也去不掉。

转化为01背包问题求解
既然01背包问题是最基本的背包问题,那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是,考虑到第i种物品最多选V/c[i]件,于是可以把第i种物品转化为V/c[i]件费用及价值均不变的物品,然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度,但这毕竟给了我们将完全背包问题转化为01背包问题的思路:将一种物品拆成多件物品.

这个问题有O(VN)个状态要解,而且求每个状态的时间是O(vCi),总的复杂度上界是O(NV∑VCi),还是比较大的。
http://crescentmoon.info/2013/08/05/bag-problem-1/
void BasicCompletePack() //O(NVsum(V/C_i))的算法
{
memset(F,0,sizeof(F));
for(int i=1;i<=N;i++)
{
for(int v=1;v<=V;v++)
{
int max=F[i-1][v];
int kmax=v/C[i];
F[i][v]=F[i-1][v]; //还是默认不加入物品,这是k=0的情况
if(kmax>=1)//v>=c[i];
{
for(int k=1;k<=kmax;k++)
{
if(F[i-1][v-k*C[i]]+k*W[i]>max)
{
max=F[i-1][v-k*C[i]]+k*W[i];
}
}
F[i][v]=max;
}
}
}
}
f[i][j]=max(f[i][j],f[i-1][j-k*c[i]]+k*w[i]);(1<=i<=N,0<=k<=v/c[i],0<=j<=V);
06    scanf("%d%d",&v,&n);
07    for (i=1;i<=n;i++) scanf("%d%d",&c[i],&w[i]);
08    for (i=1;i<=n;i++)
09    {
10        t=v%c[i];
11        t=(v-t)/c[i];
12        for (k=0;k<=t;k++)
13        {
14            for (j=0;j<=v;j++)
15            {
16                if ((k*c[i]<=j)&&(f[i][j]<f[i-1][j-k*c[i]]+k*w[i]))
17                    f[i][j]=f[i-1][j-k*c[i]]+k*w[i];
18            }
19        }
20    }
21    printf("%d",f[n][v]);
http://www.ahathinking.com/archives/108.html
基本实现
    for(i = 0; i < N; ++i)
    {
        for(j = 0; j <= V; ++j)
        {
            if(i > 0)
            {
                maxV[i][j] = maxV[i-1][j];
                if(j/weight[i] >= 1)
                {
                    int max_tmp = 0;
                    for(k = 1; k <= j/weight[i]; ++k)
                    {
                        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];
                        }
                    }
                    maxV[i][j] = maxV[i][j] > max_tmp ? maxV[i][j] : max_tmp;
                }
            }else
            {
                if(j/weight[0] >= 1)
                {
                    maxV[0][j] = j/weight[0] * value[0];
                }
            }
        }
    }


http://www.ahathinking.com/archives/108.html
更高效的转化方法是:把第i种物品拆成费用为c[i]*2^k、价值为w[i]*2^k的若干件物品,其中k满足c[i]*2^k<=V。这是二进制的思想,因为不管最优策略选几件第i种物品,总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log V/c[i])件物品,是一个很大的改进。

完全背包二进制拆分思想
这种实现方式是对完全背包的基本实现做了一个优化,叫“二进制拆分”。所谓“拆分物体”就是将一种无限件物品拆分成有效的几件物品,拆分物体的目的是通过减少物品个数来降低复杂度。
在完全背包中,每种物品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]  }

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];
     }
}

O(VN)的算法
这个算法使用一维数组,先看伪代码:
for i=1..N
    for v=0..V
        f[v]=max{f[v],f[v-cost]+weight}

你会发现,这个伪代码与P01的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢?首先想想为什么P01中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说,这正是为了保证每件物品只选一次,保证在考虑“选入第i件物品”这件策略时,依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。

而现在完全背包的特点恰是每种物品可选无限件,所以在考虑“加选一件第i种物品”这种策略时,却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]],所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。
值得一提的是,上面的伪代码中两层for循环的次序可以颠倒。这个结论有可能会带来算法时间常数上的优化。
这个算法也可以以另外的思路得出。例如,将基本思路中求解f[i][v-c[i]]的状态转移方程显式地写出来,代入原方程中,会发现该方程可以等价地变形成这种形式:
f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}
将这个方程用一维数组实现,便得到了上面的伪代码。
最后抽象出处理一件完全背包类物品的过程伪代码:
procedure CompletePack(cost,weight)
    for v=cost..V
        f[v]=max{f[v],f[v-c[i]]+w[i]}

完全背包中的逆向思维
我们反过来想,先确定背包v1容量时的物品的最优策略,然后考虑v容量下,对于随着可选物品i的增多,考虑背包的最大价值是否有变化。 

状态转移方程为
F[i,v]=max{F[i−1][v],F[i][v−Ci]+Wi}

这里F[i−1][v]是不选第i个物品时,背包的最大价值,F[i][v−Ci]+Wi是选了物品i时,背包的最大价值。需要注意的是,在v增长的过程中,物品i有可能被选择多次,因为每轮v的循环都要考虑一次物品i。

void RerVerseCompletePack()
{
memset(F,0,sizeof(F));
for(int v=1;v<=V;v++)
{
for(int i=1;i<=N;i++)
{
if(v<C[i])
{
F[i][v]=F[i-1][v];//如果物品i放不进去,选择前i-1中最好的结果
}
else
{
F[i][v]=max(F[i-1][v],F[i][v-C[i]]+W[i]);
}
}
}
}
 

设F[i][j]表示出在前i种物品中选取若干件物品放入容量为j的背包所得的最大价值。那么对于第i种物品的出现,我们对第i种物品放不放入背包进行决策。如果不放那么F[i][j]=F[i-1][j];如果确定放,背包中应该出现至少一件第i种物品,所以F[i][j]种至少应该出现一件第i种物品,即F[i][j]=F[i][j-C[i]]+W[i]。为什么会是F[i][j-C[i]]+W[i]?因为F[i][j-C[i]]里面可能有第i种物品,也可能没有第i种物品。我们要确保F[i][j]至少有一件第i件物品,所以要预留C[i]的空间来存放一件第i种物品。
状态方程为:
                           (2-2)
  1. for i←1 to N  
  2.   
  3.     do for j←1 to V  
  4.   
  5.         F[i][j] ← F[i-1][j]  
  6.   
  7.         if(j >= C[i])  
  8.   
  9.             then F[i][j] ← max(F[i][j],F[i][j-C[i]]+ W[i])  
  10.   
  11. return F[N][V] 


我们知道,在01背包和完全背包的实现中,都是针对每种物品进行讨论,即外循环都是for i=0…n,然后每种物品对于容量v的变化而求得最大价值;
在完全背包中,由于物品的件数无限,所以我们可以倒过来想,我们针对每个容量讨论,外循环为容量,对于每个容量j,我们求j对于所有物品能装载的最大价值,这样一来我们就能将时间复杂度降为O(N*V)了。
int maxValue[201][11]; /* 记录子问题的各状态 */
int weight[11];
int value[11];
int maxV[201]; /* 记录子问题的最优解 */
int V, N;
    int i, j;
    scanf("%d %d",&V, &N);
    for(i = 0; i < N; ++i)
    {
        scanf("%d %d",&weight[i],&value[i]);
    }
    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;
    }
    printf("%d",maxV[V]);
完全背包使用一维数组
对于01背包和完全背包,无论是空间复杂度还是时间复杂度,最优的方法还是使用一维数组进行实现。
基于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;
        }
    }
    printf("%d",maxV[V]);

  1. for i←1 to N  
  2.   
  3.     do for k←C[i] to V  
  4.   
  5.         F[k] ← max(F[k],F[k-C[i]]+W[i])  
  6.   
  7. return F[V]  

//时间复杂度O(VN),空间复杂度为O(VN)
  1.     for(int i = 1; i <= nLen; i++)  
  2.     {  
  3.         for(int j = 1; j <= nCapacity; j++)  
  4.         {  
  5.             Table[i][j] = Table[i-1][j];  
  6.             if(j >= Weight[i-1] && Table[i][j] < Table[i][j-Weight[i-1]]+Value[i-1])  
  7.             {  
  8.                 Table[i][j] = Table[i][j-Weight[i-1]]+Value[i-1];  
  9.                 Path[i][j]=1;  
  10.             }  
  11.         }  
  12.     }  
  13.   
  14.     int i = nLen, j = nCapacity;  
  15.     while(i > 0 && j > 0)  
  16.     {  
  17.         if(Path[i][j] == 1)  
  18.         {  
  19.             cout << Weight[i-1] << " ";  
  20.             j -= Weight[i-1];  
  21.         }  
  22.         else  
  23.             i--;  
  24.     }  
//时间复杂度O(VN),不考虑路径空间复杂度为O(V),考虑路径空间复杂度为O(VN)
  1.     for(int i = 0; i < nLen; i++)  
  2.     {  
  3.         for(int j = Weight[i]; j <=nCapacity; j++)  
  4.         {  
  5.             if(Table[j] < Table[j-Weight[i]]+Value[i])  
  6.             {  
  7.                 Table[j] = Table[j-Weight[i]]+Value[i];  
  8.                 Path[i+1][j] = 1;  
  9.             }  
  10.         }     
  11.     }  
  12.   
  13.     int i = nLen, j = nCapacity;  
  14.     while(i > 0 && j > 0)  
  15.     {  
  16.         if(Path[i][j] == 1)  
  17.         {  
  18.             cout << Weight[i-1] << " ";  
  19.             j -= Weight[i-1];  
  20.         }  
  21.         else  
  22.             i--;  
  23.     }  
Related:
http://massivealgorithms.blogspot.com/2015/06/unbounded-knapsack-problem.html

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