背包問題
定義
我們有 n 種物品，物品j的重量為 wj ，價格為 pj 。
我們假定所有物品的重量和價格都是非負的。背包所能承受的最大重量為W。
如果限定每種物品隻能選擇0個或1個，則問題稱為0-1背包問題
可以用公式表示為：
最大化： ∑nj=1xjpj
受限于： ∑nj=1xjwj≤W
如果限定物品j最多隻能選擇bj個，則問題稱為有界背包問題。
可以用公式表示為：
最大化： ∑nj=1xjpj
受限于： ∑nj=1xjwj≤Wxj∈(0,1,…,bj)
如果不限定每種物品的數量，則問題稱為無界背包問題。
各類複雜的背包問題總可以變換為簡單的0-1背包問題進行求解。
分數背包問題
定義
背包問題中的 xj 可以取的值為任意實數，包括分數，上限為物體 j 的數目。對于分數背包問題，我們采用貪心算法，每次選擇餘下物品中單價最大的。
例題
三種物體，價值分别是：60,100,120，重量分别是：10,20,30，背包所能承受的總重量為：50；求解最大的價值裝在方案。
代碼
注：1.定義了結構體用以儲存價值，重量和單價
2.排序使用的快排，按照單價排序。
//============================================================================
// Name : knapsack.cpp
// Author : selous
// Version :
// Copyright : Your copyright notice
// Description : fraction knapsack problems;greedy strategy
//============================================================================
#include <iostream>
using namespace std;
const int N = ;//types of things;
typedef struct goods{
float weigh;//the weigh of the goods;
float value;//the value of the goods;
float price;//the per weigh price of goods;
}goods;
void knapsack(int knapsackWeigh,goods *g,float *x);
void Qsort(goods *g,int low,int high);
int partition(goods *g,int low,int high);
void sort(goods *g);
void print(goods *g,int low,int high);
int main() {
float knapsackWeigh = ;//the weigh of knapsack
goods g[N+]={{,,},{,,},{,,},{,,}};
int i;
for(i=;i<=N;i++){
g[i].price=g[i].value/g[i].weigh;
}
// int weigh[N] = {10,20,30};//the weigh of each things
// int value[N] = {60,100,120};//the volume of each things
float x[N+]={,,,};//the num of each things in the knapsack
knapsack(knapsackWeigh,g,x);//solve the knapsack problem
cout<<"背包的總重量為："<<knapsackWeigh<<endl;
print(g,,N);
for(int i=;i<=N;i++){
//print the num of things in the knapsack;
cout<<"第"<<i<<"個物體的個數為："<<x[i]<<endl;
}
return ;
}
void knapsack(int knapsackWeigh,goods *g,float *x){
sort(g);
//sort the goods according to the price;
int i;
for(i=;i<=N;i++){
if(knapsackWeigh<g[i].weigh){
break;
}
x[i]+=;
knapsackWeigh-=g[i].weigh;
}
if(i<=N){
x[i] = knapsackWeigh/g[i].weigh;
}
}
//first:set a pivot key to divide the array.
//second:divide the array to different sub array
int partition(goods *g,int low,int high){
g[]=g[low];
float pivotkey = g[low].price;
//divide according the pivotkey
while(low<high){
while(low<high&&g[high].price<=pivotkey) --high;
g[low]=g[high];
while(low<high&&g[low].price>=pivotkey) ++low;
g[high]=g[low];
}
//recover the pivot key to the middle of the array.
g[low]=g[];
return low;
}
//quick sort
void Qsort(goods *g,int low,int high){
if(low < high){
int pivotloc = partition(g,low,high);
Qsort(g,low,pivotloc-);
Qsort(g,pivotloc+,high);
}
}
void sort(goods *g){
Qsort(g,,N);
}
void print(goods *g,int low,int high){
cout<<"g的取值為：";
for(int i=low;i<=high;i++){
cout<<"第"<<i<<"個物體的屬性為("<<g[i].weigh<<","
<<g[i].value<<","<<g[i].price<<")"<<endl;
}
}
關于貪心政策，在acm中看到一個特别好的題目。貼在下面，之後會寫一篇部落格貼上對應答案。過河問題：
在漆黑的夜裡，N位旅行者來到了一座狹窄而且沒有護欄的橋邊。如果不借助手電筒的話，大家是無論如何也不敢過橋去的。不幸的是，N個人一共隻帶了一隻手電筒，而橋窄得隻夠讓兩個人同時過。如果各自單獨過橋的話，N人所需要的時間已知；而如果兩人同時過橋，所需要的時間就是走得比較慢的那個人單獨行動時所需的時間。問題是，如何設計一個方案，讓這N人盡快過橋。
輸入
第一行是一個整數T(1<=T<=20)表示測試資料的組數
每組測試資料的第一行是一個整數N(1<=N<=1000)表示共有N個人要過河
每組測試資料的第二行是N個整數Si,表示此人過河所需要花時間。
輸出
輸出所有人都過河需要用的最少時間
題目來源：http://acm.nyist.net/JudgeOnline/problem.php?pid=47
0/1背包問題
定義
背包問題中的xj取值為0或者1，對于這種典型的背包問題，采用動态規劃的思想實作。
貼一個對0/1背包問題講解比較詳細的部落格：http://blog.csdn.net/mu399/article/details/7722810
其中動态規劃涉及的遞推關系為： L[i][j]=max{L[i−1][j],L[i−1][j−wi]+vi} 取不放入背包和放入背包情況下的value的較大值。
例題
背包容量為9,4種物體的體積為：2,3,4和5；價值分别為：3,4,5,7求使得背包價值最大的選擇。
代碼
//============================================================================
// Name : bknapsack.cpp
// Author : selous
// Version :
// Copyright : Your copyright notice
// Description : 0/1 knapsack problem;Dynamic programming
//============================================================================
#include <iostream>
using namespace std;
#define debug 1
const int N=;//the numble of goods;
const int knapsackWeight=;//the max weight of the knapsack
typedef struct goods{
int weight;
int value;
}goods;
int main() {
goods g[N+]={{,},{,},{,},{,},{,}};
int value[N+][knapsackWeight+];
int i,j;
//initial the first column of the value matrix;
for(i=;i<N+;i++){
value[i][]=;
}
//initial the first row of the value matrix;
for(j=;j<knapsackWeight+;j++){
value[][j]=;
}
if(debug==){
for(i=;i<N+;i++){
for(j=;j<knapsackWeight;j++){
cout<<value[i][j]<<" ";
}
cout<<endl;
}
}
for(i=;i<N+;i++){
for(j=;j<knapsackWeight+;j++){
// cout<<"hello"<<i<<j<<endl;
//do not put the ith goods into the knapsack;
value[i][j]=value[i-][j];
//if the ith can put into the knapsack;
if(g[i].weight<=j){
//put the ith goods intp the knapsack;
int tempValue=value[i-][j-g[i].weight]+g[i].value;
//compare the values of put and notput
if(value[i][j]<tempValue){
value[i][j]=tempValue;
}
}
}
}
for(i=;i<N+;i++){
for(j=;j<knapsackWeight+;j++){
cout<<value[i][j]<<" ";
}
cout<<endl;
}
cout<<"背包最大容量為：";
cout<<value[N][knapsackWeight];
return ;
}
完全背包問題
定義
背包問題中的 xi 的取值可以為所有的正整數。其中動态規劃涉及的遞推關系為： L[i][j]=max{L[i−1][j],L[i][j−wi]+vi} 取不放入背包和放入背包情況下的value的較大值。
關于該遞推關系的思考：真實的遞推關系應該是 L[i][j]=max{L[i][j−xi∗wi]+xi∗vi}0≤xi∗wi≤j
1.當 xi=0 時，其值為 L[i−1,j] 。
2.當 xi≠0 時， L[i][j−wi]+vi≥L[i][j−2wi]+2vi=L[i][j−2wi]+vi+vi ,其中 L[i][j−wi] 為物體種類為 i ，背包大小j−wi的最大值，故 L[i][j−wi]≥L[i][j−2wi]+vi ,
綜上兩點可以得到，該遞推關系可以簡化為 L[i][j]=max{L[i−1][j],L[i][j−wi]+vi}
例題
背包容量為9,4種物體的體積為：2,3,4和5；價值分别為：3,4,5,7求使得背包價值最大的選擇。
代碼
隻需要将上題的遞推關系改為：
int tempValue = valueMatrix[i][j-g[i].weight]+g[i].value;
貼一道ACM中比較好玩的關于完全背包的問題：http://ac.jobdu.com/problem.php?pid=1454
關于上面這個題目需要注意的該題是完全背包的拓展，求解是背包可容納的最小值，是以需要将矩陣初始化為最大值，如999999，遞推關系取最小值。對于算法執行後仍然為999999的，屬于不可能出現的情況。
多重背包問題
對于多重背包問題，在網上沒有找到特别好的思想去解決。主流方法就是将問題轉化為0/1背包問題，下面這篇部落格也提到了二進制轉化。下次有時間試試。
http://www.cnblogs.com/tanky_woo/archive/2010/07/31/1789621.html
——2017.2.16
![leetcode_17.Letter Combinations of a Phone Number[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)