一个容量为V的背包，有N种物品（每种物品一个），每个物品对应一个重量和价值。求最大能装多少价值物品。
状态转移方程：dp[i][j]=max(dp[i-1][j] , dp[i-1][j-w[i]]+v[i]);
for(int i=1;i<=N;++i) { far(int j=0;j<=V;++j) { dp[i][j]=dp[i-1][j]; if(j>=costs[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-costs[i]]+gains[i]); } }节省空间时：遍历每一物品，解决从前几个物品中选的子问题。对于每一容量，逆序遍历，因为是与前几个物品状态下求出的dp值有关。这样保证了每一物品只被选一次，因为第i次循环中状态dp[i][v]是由dp[i-1][v]推出。这样递推保证了dp[i][j]=dp[i-1][j]被执行，所以不是正好要填满
for(int i=0;i<N;++i) for(int j=V;j>=w[i];--j) dp[j]=max(dp[j] , dp[j-w[i]]+v[i]);一个容量为V的背包，有N种物品（每种物品无限个），每个物品对应一个重量和价值。求最大能装多少价值物品。
只需用一维数组即可dp。因为要考虑加选一件i物品。
因为每个物品 都有可能选多个，所以要正序遍历，因为dp[i-1][j-w[i]]可以由多个组成。
dp[0]=0 for(int i=0;i<N;++i) for(int j=w[i];j<=V;++j) dp[j]=max(dp[j] , dp[j-w[i]]+v[i]);可以理解为状态转移方程为dp[i][j]=max(dp[i-1][j] , dp[i][j-w[i]]+v[i])
多重背包：
二进制思想拆分：多重背包中的一个物品--变成-->0-1背包中的多个物品
容量：2^0 2^1 2^2 2^k m-∑前面 ***保证k达到最大值
价值：2^0*c 2^1*c 2^2*c 2^k*c (m-∑前面 )*c
/************************************背包板子*/ inline void ZeroOnePack(int weight,int value){ for(int i = bag; i>=weight ; --i) dp[i] = max(dp[i],dp[i-weight]+value); } inline void CompletePack(int weight,int value){ for(int i = weight ; i <= bag ; ++i) dp[i] = max(dp[i],dp[i-weight]+value); } inline void MultiplePack(int weight,int value , int number){//二进制分解 if(number*weight >= bag){ CompletePack(weight,value); return; } int k = 1; while(number > k){ ZeroOnePack(weight*k,value*k); number -= k; k <<= 1; } if(number > 0) ZeroOnePack(weight*number,value*number); } /********************************************/theme:n种游戏，每种游戏只能玩一次，玩第i种游戏花费wi元、获得hi开心值，现有m元，问最大能获得多少开心值?1≤N,M≤10^5,1≤Pi,Wi≤10
solution:咋一看就是01背包,但是范围n,m太大,直接01背包o(n^2)铁定超时.注意到pi,范围很小,本质不同的组合最多也就10*10=100种,所以我们可以转化一下成多重背包.对于确定的pi,wi确定是该状态的游戏个数,对于所重背包采用上述二进制分解数量,最多1e5,分解为1000件,这样复杂度为O(1000M)
#include <bits/stdc++.h> using namespace std; const int N = 1e5+777; int num[11][11];// i 为 花费 ， j 为 收益 ， num 记录个数 int dp[N]; int bag; /************************************背包板子*/ inline void ZeroOnePack(int weight,int value){ for(int i = bag; i>=weight ; --i) dp[i] = max(dp[i],dp[i-weight]+value); } inline void CompletePack(int weight,int value){ for(int i = weight ; i <= bag ; ++i) dp[i] = max(dp[i],dp[i-weight]+value); } inline void MultiplePack(int weight,int value , int number){ if(number*weight >= bag){ CompletePack(weight,value); return; } int k = 1; while(number > k){ ZeroOnePack(weight*k,value*k); number -= k; k <<= 1; } if(number > 0) ZeroOnePack(weight*number,value*number); } /********************************************/ int main(){ int n; scanf("%d%d",&n,&bag); while(n--){ int x,y; scanf("%d%d",&x,&y); ++num[x][y];//统计物品 } for(int i=1;i<=10;++i) for(int j=1;j<=10;++j) MultiplePack(i,j,num[i][j]); printf("%d\n",dp[bag]); }theme:N元钱换为零钱，有多少不同的换法？币值包括1 2 5分，1 2 5角，1 2 5 10 20 50 100元。
solution:典型完全背包。
#include<bits/stdc++.h> using namespace std; #define far(i,t,n) for(int i=t;i<n;++i) typedef long long ll; typedef unsigned long long ull; int a[13]={1,2,5,10,20,50,100,200,500,1000,2000,5000,10000}; ll dp[100010]; const int p=1e9+7; void getDp() { far(j,0,100002) dp[j]=1; far(i,1,13) for(int j=a[i];j<100001;++j) dp[j]=(dp[j]+dp[j-a[i]])%p; } int main() { getDp(); int n; scanf("%d",&n); printf("%lld\n",dp[n]); } /*************************************************** * author:sgx * date:2013/09/19 * problem:01背包第k优解 * 分析：第K优解问题 * 其基本思想是将每个状态都表示成有序队列，将状态转移方程中的max/min转化成有序队列的合并。 * 如果要求第K优解，那么状态f[i][v]就应该是一个大小为K的数组f[i][v][1..K]。 * 其中f[i][v][k]表示前i个物品、背包大小为v时，第k优解的值。 显然f[i][v] [1..K]这K个数是由大到小 * 排列的，所以我们把它认为是一个有序队列。 * 然后原方程就可以解释为：f[i][v]这个有序队列是由f[i-1][v]和f[i-1][v-c[i]]+w[i]这两个有序队列 * 合并得到的。有序队列 f[i-1][v]即f[i-1][v][1..K]，f[i-1][v-c[i]]+w[i]则理解为 * 在f[i-1][v-c[i]][1..K]的每个数上加上w[i]后得到的有序队列。合并这两个有序队列并将结果的 * 前K项储存到f[i][v][1..K]中的复杂度是O(K)。最后的答案是f[N][V][K]。 * hint：和普通01背包是相同的，也可以降维。。 ***************************************************/ #include <cstdio> #include <cmath> #include <cstring> using namespace std; const int maxn=1001; int dp[maxn][33];//dp[i][j]表示i体积下第j优解 int c[maxn],w[maxn]; inline int max(int a,int b) { return a>b?a:b; } int main() { int T; scanf("%d",&T); while(T--) { int n,m,i,j,k,p,a[33],b[33]; scanf("%d%d%d",&n,&m,&k); for(i=0;i<n;i++) scanf("%d",&w[i]); for(i=0;i<n;i++) scanf("%d",&c[i]); memset(dp,0,sizeof(dp)); for(i=0;i<n;i++) { for(j=m;j>=c[i];j--) { for(p=1;p<=k;p++) { a[p]=dp[j-c[i]][p]+w[i]; //在dp[i]=max(dp[j],dp[j-c[i]]+w[i])中产生后续优解，小的为次优 b[p]=dp[j][p]; } a[p]=b[p]=-1; int x,y,z; x=y=z=1; while(z<=k&&(a[x]!=-1||b[y]!=-1))//产生分歧后找到其中最大的k的保留 { if(a[x]>b[y]) { dp[j][z]=a[x]; x++; } else { dp[j][z]=b[y]; y++; } if(dp[j][z]!=dp[j][z-1])//去掉重复了的优解 z++; } } } printf("%d\n",dp[m][k]); } return 0; }sort+unique:
#include<string.h> #include<string> #include<stdio.h> #include<stdlib.h> #include <algorithm> #include <map> #include <set> #include <functional> using namespace std; int T,N,V,K; int value[1008]; int volume[1008]; int main() { scanf("%d",&T); while(T--) { int dp[1008][38]={ 0}; scanf("%d %d %d",&N,&V,&K); for(int i = 0;i < N;++i) scanf("%d",value+i); for(int i = 0;i < N;++i) scanf("%d",volume+i); for(int i = 0;i < N;++i) { for(int j = V;j >= volume[i];--j) { int a[70]={0}; int cnt = 0; for(int k = 0;k < K;++k) { a[cnt++] = dp[j][k]; a[cnt++] = dp[j-volume[i]][k]+value[i]; } sort(a,a+cnt,greater<int>());//不能直接用nth_element，因为要去重做 int* cnt2 = unique(a,a+cnt) ; while(cnt2 != a+cnt)//去完重，其余的值为0 { *cnt2 = 0; ++cnt2; } copy(a,a+K,dp[j]); } } printf("%d\n", dp[V][K-1]); } }theme:给定n枷银行的钱数与小偷被抓住的概率，问被抓住的概率不超过给定的p的情况下能偷到的最大钱数。0 < T <= 100 0.0 <= P <= 1.0 0 < N <= 100 0 < Mj <= 100 0.0 <= Pj <= 1.0
solution:从题意可以看出是01背包问题，但不能简单地将概率作为容量，因为概率是小数，不能作为下标，且该题没有说明小数的位数，所以也不能转化为整数作为下标。我们可以转化一下：因为数据范围不大，所以可以把获得的钱数作为容量，为方便概率计算，令dp[i]为获得钱数i时（注意01背包算的是正好装满）的最大成功率，则算出后从大到小遍历dp[i]，第一个概率值>=1-p的i即为结果。
#include<bits/stdc++.h> using namespace std; #define far(i,t,n) for(int i=t;i<n;++i) typedef long long ll; typedef unsigned long long ull; using namespace std; int lost[200]; double gain[200]; double dp[10010];//表示获得i元的最大成功概率。 void getDp(int n,double gains,int losts) { //cout<<gains<<" "<<losts<<":\n"; for(int i=n;i>=losts;--i) { dp[i]=max(dp[i],dp[i-losts]*gains); //cout<<i<<" "<<dp[i]<<endl; } } int main() { int t; cin>>t; while(t--) { double p; int n; scanf("%lf%d",&p,&n); int sum=0; far(i,0,n) scanf("%d%lf",&lost[i],&gain[i]),gain[i]=1-gain[i],sum+=lost[i]; memset(dp,0,sizeof(dp)); dp[0]=1; for(int i=0;i<n;++i) getDp(sum,gain[i],lost[i]); int ans=sum; for(int i=sum;i>=0;--i) if(dp[i]>=(1-p)) { ans=i; break; } printf("%d\n",ans); } } /* 3 0.00 3 1 0.02 2 0.03 3 0.05 2 */每种物品可能有多个（定值），把它们看做单独的一个一个的物品转化为01背包。
theme:n中物品，每种物品可能有多个，价值不同，现分给两个人A，B，要求按价值尽量平分且A得到的价值要>=B的。0 < N <= 50，0 < M <= 100,0 < V <= 50.
solution:最终两人的价值之和是定值sum已知,的因为要求尽量平分且B的不能大，说明B获得的价值最大为sum/2,所以用sum/2作为B的背包容量，因为数据范围很小，直接将多重背包转为01背包即可。
#include<bits/stdc++.h> #include<vector> #include<algorithm> using namespace std; #define far(i,t,n) for(int i=t;i<n;++i) #define pk(a) push_back(a) typedef long long ll; typedef unsigned long long ull; using namespace std; int gains[5050]; int dp[300030]; void getDp(int gain,int cost,int maxv) { for(int i=maxv;i>=cost;--i) dp[i]=max(dp[i],dp[i-cost]+gain); } int main() { int n; while(scanf("%d",&n)&&n>=0) { memset(dp,0,sizeof(dp)); int sum=0,cnt=0; far(i,0,n) { int v,m; scanf("%d%d",&v,&m); far(j,0,m) gains[cnt++]=v; sum+=v*m; } int maxv=sum/2; for(int i=0;i<cnt;++i) getDp(gains[i],gains[i],maxv); printf("%d %d\n",sum-dp[maxv],dp[maxv]); } }
