背包问题
定义
我们有
我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。
如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题
可以用公式表示为：
最大化：
受限于：
如果限定物品j最多只能选择bj个，则问题称为有界背包问题。
可以用公式表示为：
最大化：
受限于：
如果不限定每种物品的数量，则问题称为*背包问题。
各类复杂的背包问题总可以变换为简单的0-1背包问题进行求解。
分数背包问题
定义
背包问题中的
例题
三种物体，价值分别是：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 = 3;//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 = 50;//the weigh of knapsack
goods g[N+1]={{0,0,0},{10,60,0},{20,100,0},{30,120,0}};
int i;
for(i=1;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+1]={0,0,0,0};//the num of each things in the knapsack
knapsack(knapsackWeigh,g,x);//solve the knapsack problem
cout<<"背包的总重量为："<<knapsackWeigh<<endl;
print(g,1,N);
for(int i=1;i<=N;i++){
//print the num of things in the knapsack;
cout<<"第"<<i<<"个物体的个数为："<<x[i]<<endl;
}
return 0;
}
void knapsack(int knapsackWeigh,goods *g,float *x){
sort(g);
//sort the goods according to the price;
int i;
for(i=1;i<=N;i++){
if(knapsackWeigh<g[i].weigh){
break;
}
x[i]+=1;
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[0]=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[0];
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-1);
Qsort(g,pivotloc+1,high);
}
}
void sort(goods *g){
Qsort(g,1,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背包问题
定义
背包问题中的
贴一个对0/1背包问题讲解比较详细的博客：http://blog.csdn.net/mu399/article/details/7722810
其中动态规划涉及的递推关系为：
例题
背包容量为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=4;//the numble of goods;
const int knapsackWeight=9;//the max weight of the knapsack
typedef struct goods{
int weight;
int value;
}goods;
int main() {
goods g[N+1]={{0,0},{2,3},{3,4},{4,5},{5,7}};
int value[N+1][knapsackWeight+1];
int i,j;
//initial the first column of the value matrix;
for(i=0;i<N+1;i++){
value[i][0]=0;
}
//initial the first row of the value matrix;
for(j=0;j<knapsackWeight+1;j++){
value[0][j]=0;
}
if(debug==0){
for(i=0;i<N+1;i++){
for(j=0;j<knapsackWeight;j++){
cout<<value[i][j]<<" ";
}
cout<<endl;
}
}
for(i=1;i<N+1;i++){
for(j=1;j<knapsackWeight+1;j++){
// cout<<"hello"<<i<<j<<endl;
//do not put the ith goods into the knapsack;
value[i][j]=value[i-1][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-1][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=0;i<N+1;i++){
for(j=0;j<knapsackWeight+1;j++){
cout<<value[i][j]<<" ";
}
cout<<endl;
}
cout<<"背包最大容量为：";
cout<<value[N][knapsackWeight];
return 0;
}
完全背包问题
定义
背包问题中的
关于该递推关系的思考：真实的递推关系应该是
1.当
2.当
综上两点可以得到，该递推关系可以简化为
例题
背包容量为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