每日一题(7)——0-1背包问题
问题描述：
一个小偷去偷金库（这个小偷比较NB~），带了一个能承重N的背包，金库里放了不同品质的金砖，以（重量，价值）形式给出，问小偷怎样拿，获利最大？
输入：
第一行：金砖数目， 背包承重能力；
其他行：金砖重量， 金砖价值
输出：
带走金砖数目；带走最大价值；金砖序号
input：
3 50
10 60
20 100
30 120
output:
2
180
1 3
这道题是典型的动态规划，跟公正陪审团问题的解法相似：
利用
f[j][k]：j=带走金砖数目，k=金砖重量，f[j][k]：带走金砖数目=j，且金砖重量=k时的价值；
分几层循环，
最外层遍历所有的数量j：[0,n)
第二层遍历所有可能的重量：k:[0,M] 判断f[j][k]>=0来决定是否进入循环（根据j 来判断，根据j 计算j+1）
内层遍历所有的金砖i：[1,n]
if( f[j][k]+v[i] > f[j+1][k+w[i]]&&k+w[i]<=M)
{
检测i是否出现过，若没有出现过 f[j+1][k+w[i]] = f[j][k]+v[i];（初始条件是f[0][0]=0;）
}
#include<stdio.h>#include<stdlib.h>#include<iostream>#include<string.h>#include <set>using namespace std;int f[30][1000];int Path[30][1000];int w[300];//质量;int v[300]; //价值;set<int> index;//存放最终方案int main(){int i,j,k;int t1,t2;int n,M;//n为数量，m为最大重量;while(scanf("%d %d",&n,&M)){if(n==0&&M==0)break;for(i=1;i<=n;i++)scanf("%d %d",&w[i],&v[i]);memset(f,-1,sizeof(f));memset(Path,0,sizeof(Path));f[0][0]=0;//初始化条件，根据f[0][0]推以后的结果for(j=0;j<n;j++)//每次循环选出第j个物品,最多n个;{for(k=0; k <=M; k++)//可能的重量为[0,M]; if(f[j][k]>=0)//方案f[j,k]可行，从f[0][0]开始; {for(i=1; i<=n; i++)if( f[j][k]+v[i] > f[j+1][k+w[i]]&&k+w[i]<=M)//若f[j+1][k+w[i]]已经有值，则保存较大的一个;{t1=j;t2=k;while(t1>0&&Path[t1][t2]!=i)//验证i是否在前面出现过;{t2-=w[Path[t1][t2]];//减前一个元素的重量;t1--;}if(t1==0)//若i未出现过;{f[j+1][k+w[i]] = f[j][k]+v[i];Path[j+1][k+w[i]]=i;} } } }int maxNum=0,maxV=0,maxW=0;for (int i=1; i<=n; i++){for (int j=0; j<=M; j++)//注意必须 =M{if(maxV<f[i][j]) {maxV=f[i][j];maxNum=i;maxW=j;}}}cout<<"MAX Value: "<<maxV<<endl;cout<<"MAX num: "<<maxNum<<endl;index.clear();for (int i=0; i<maxNum; i++){int id=Path[maxNum-i][maxW];//若直接输出，由于递归，则是乱序的;index.insert(id);maxW -= w[id];}cout<<endl;for(set<int>::iterator iter=index.begin(); iter!=index.end(); iter++) cout<<*iter<<" ";} return 0; }
0-1背包问题和陪审团问题都是属于动态规划中的同一类问题，这种问题比较难做（我比较菜鸟，这是我的感觉啊~）
这类问题关键要换个思路，要给最优解添加约束条件：f[j][k],k金砖重量就是约束条件，要根据约束条件k进行迭代k[0,M]，迭代的过程要首先判断是否符合题意：if(f[j][k]>=0)，
最内层要不断的组合没有计算过的元素，根据已知推未知f[j+1][k+w[i]] = f[j][k]+v[i];
另外部分背包问题可以用贪心算法解决（相当于小偷偷的是金沙）背包问题还有很多种，这都以后再讲。
续……
读完背包九讲发现我解题的方法略复杂，其实利用一维数组就可以实现动态规划，
根据状态转移方程：f[w]=max{f[w], f[w-c]+v}
f[w]表示在重量为w时的最优解，
参考网上一位大牛重新写的代码：
#include <iostream>using namespace std;const int nMax=400;//待选物品数;const int mMax=10000; //最大载重;struct{int wei,val;}node[nMax];int main(){int m, n, i ,w ,dp[mMax];while(cin>>n>>m)//n为待选物品数量，m为最大载重量;{if(m==0&&n==0) break;for (i=1; i<=n;i++)cin>>node[i].wei>>node[i].val;memset(dp, 0, (m+1)*sizeof(int));for (i=1; i<=n; i++)for ( w=m; w>=node[i].wei; w-- )if ( dp[w] < dp[w - node[i].wei] + node[i].val )dp[w] = dp[w - node[i].wei] + node[i].val;cout<<dp[m]<<endl;}}
DynamicProgram问题也真是博大精深呐~ 题在精而不在多~