背包问题小结持续更新算法基础篇（七）

View Code
  1 // 背包问题.cpp : 定义控制台应用程序的入口点。
  2 //
  3 //来自背包九讲
  4 
  5 
  6 /****************************/
  7 /*
  8 设计者：cslave
  9 代码说明：  背包问题
 10 */
 11 #include "stdafx.h"
 12 #include <iostream>
 13 using namespace std;
 14 #define NumItem 10
 15 #define Max 100
 16 typedef int CapType;
 17 typedef int ValueType;
 18 CapType Capacity=Max;
 19 
 20 
 21 ValueType f[NumItem][Capacity];
 22 CapType   Cost[NumItem];
 23 ValueType Weight[NumItem];
 24 int       Amount[NumItem];
 25 
 26 
 27 /*****************01背包问题**************************/
 28 /*
 29 题目：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
 30 
 31 状态转移方程：
 32 
 33 用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
 34 
 35 f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
 36 
 37 时间和空间复杂度均为O(VN)
 38 
 39 伪代码：
 40 procedure ZeroOnePack(cost,weight)
 41     for v=V..cost
 42         f[v]=max{f[v],f[v-cost]+weight}
 43 
 44 
 45 procedure Pack(cost[],weight[])
 46 for i=1..N
 47     ZeroOnePack(c[i],w[i]);
 48 
 49 */
 50 /******************分割线***************************/
 51 void ZeroOnePack(CapType Cost,ValueType Weight)
 52 {
 53     for(CapType v=Capcity;v>=Cost;v--)
 54         f[v]=f[v]>f[v-Cost]+Weight?f[v]:f[v-Cost]+Weight;
 55 }
 56 
 57 void Pack()
 58 {
 59     for(int i=0;i<NumItem;i++)
 60         ZeroOnePack(Cost[i],Weight[i]);
 61 }
 62 
 63 
 64 
 65 
 66 
 67 
 68 
 69 /***********************完全背包问题***************************/
 70 /*
 71 题目：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。
 72 求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
 73 
 74 
 75 
 76 状态转移方程：
 77 用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
 78 
 79 f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
 80 
 81 时间复杂度O(VN)
 82 
 83 伪代码：
 84 for i=1..N
 85     for v=0..V
 86         f[v]=max{f[v],f[v-cost]+weight}
 87 
 88 
 89 */
 90 /************************分割线*********************************/
 91 void CompletePack(CapType Cost,ValueType Weight)
 92 {
 93     for(CapType v=Cost;v<=Capcity;v++)
 94         f[v]=f[v]>f[v-Cost]+Weight?f[v]:f[v-Cost]+Weight;
 95 }
 96 
 97 void Pack()
 98 {
 99     for(int i=0;i<NumItem;i++)
100         CompletePack(Cost[i],Weight[i]);
101 }
102 
103 
104 
105 
106 
107 
108 
109 
110 
111 
112 /*************************多重背包********************************/
113 /*
114 题目：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。
115 求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
116 
117 状态转移方程：
118 这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：
119 取0件，取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：
120 
121 f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
122 
123 复杂度是O(V*Σn[i])。
124 
125 
126 
127 伪代码：
128 procedure MultiplePack(cost,weight,amount)
129     if cost*amount>=V
130         CompletePack(cost,weight)
131         return
132     integer k=1
133     while k<amount
134         ZeroOnePack(k*cost,k*weight)
135         amount=amount-k
136         k=k*2
137     ZeroOnePack(amount*cost,amount*weight)
138 
139 procedure Pack(cost[],weight[])
140 for i=1..N
141     MultiplePack(c[i],w[i]);
142 
143 */
144 
145 /*************************分割线***********************************/
146 void MultiplePack(CapType Cost,ValueType Weight,int Amount)
147 {
148     if (Cost*Amount>=Capacity)
149     {
150         CompletePack(Cost,Weight);
151         return;
152     }
153     int k=1;
154     while(k<Amount)
155     {
156         ZeroOnePack(k*Cost,k*Weight);
157         Amount=Amount-k;
158         k=k*2;
159     }
160     ZeroOnePack(Amount*Cost,Amount*Weight);
161 }
162 
163 void Pack(CapType Cost[],ValueType weight[])
164 {
165     for(int i=0;i<NumItem;i++)
166         MultiplePack(cost[i],Weight[i],Amount[i]);
167 }
背包问题小结持续更新 算法基础篇（七）

背包问题小结持续更新算法基础篇（七）
