基础背包问题（01，完全，多重）

基础背包问题（01，完全，多重）

01背包：

有n 种不同的物品，每一种物品一件，每个物品有两个属性，wei重量（体积），val 价值，现在给一个容量为 V 的背包，问最多可带走多少价值的物品。

完全背包：

在01背包的基础上，如果物品不计件数，就是每个物品无限件的话，求出结果。

多重背包：

在01背包的基础上，每一件物品的件数是一定的（给出的），求出结果。

01背包：

状态转移方程（默认求最大价值）：dp[j]=dp[j-wei[i]]+val[i]>dp[j]?dp[j-wei[i]]+val[i]:dp[j]

for (int i=0; i=wei[i]; j--){ int t = dp[j-wei[i]]+val[i]; dp[j] =dp[j]>t?dp[j]:t; }}

完全背包：

为了累加效果，所以从前向后遍历：

for (int i=0; it?dp[j]:t; }}

多重背包：

把每一中物品的个数用二进制原理展开，转成01背包处理：

多重背包的二进制转化原理：

把一个数字展开成二进制，我们可以发现一个数字可以由小于他的1，10，10,1……组成。有一个误区，例子：10转化成二进制后：1010，设c=10, 如果直接用for(int i=1; i<=c; i<<=1) 枚举我们将得到1, 10, 100, 1000 这几个二进制数，存在结果大于10的组合（如1111）。想要将多重背包转化成01背包，就必须保证得到的数字的任意组合小于等于10。所以枚举时有这样的改进：

or(int i=1;i<=c;i<<=1){

//---

c-=i;

}

if(c>0){ //--   }

得到的数字是1,10,100,11。前三个数字的组合结果包含了0——7，最后一个数字是3，那么结果就是0——10。刚好满足条件。 另外，如果DP的初始化是0，那么得出结果是V可以不用完的，也能是用完的。当初始化为负无穷小 -inf，dp[0]=0时，结果是V刚好用完的。（看看代码就能明白）

Piggy-Bank（多重背包取最小）

​​#include #include using namespace std;typedef long long LL;LL n,V,wei[505],val[505],dp[10005];LL work(){ for(int i=0;i>t; while(t--){ LL E,F; scanf("%lld%lld",&E,&F); V=F-E; memset(dp,0x3f,sizeof(dp)); dp[0]=0; scanf("%d",&n); for(int i=0;i=0x3f3f3f3f) printf("This is impossible.\n"); else printf("The minimum amount of money in the piggy-bank is %lld.\n",ans); } return 0;}

悼念512汶川大地震遇难同胞——珍惜现在，感恩生活（简单多重背包）

​​#include #include using namespace std;int wei[505],val[505],dp[105];int n,V;int main(){ int t,m; cin>>t; while(t--){ scanf("%d%d",&V,&m); int w,v,c; n=0; for(int i=0;i0) { wei[n]=w*c; val[n++]=v*c; } } memset(dp,0,sizeof(dp)); int ans=0; for(int i=0;i=wei[i];j--){ int t=dp[j-wei[i]]+val[i]; dp[j]=dp[j]>t?dp[j]:t; ans=ans>dp[j]?ans:dp[j]; } } printf("%d\n",ans); } return 0;}

Big Event in HDU （wei=val 多重背包）

​​#include #include using namespace std;const int N=3e5+10;int wei[400],dp[N],cnt;int main(){ //freopen("cin.txt","r",stdin); int n; while(cin>>n&&(n>0)){ cnt=0; int w,c; int V=0; for(int i=0;i0) wei[cnt++]=w*c; } int V2=V/2; memset(dp,0,sizeof(dp)); for(int i=0;i=wei[i];j--){ int t=dp[j-wei[i]]+wei[i]; //price同时是重量和价值 dp[j]=t>dp[j]?t:dp[j]; } } int ans2=dp[V2],ans1=V-ans2; printf("%d %d\n",ans1,ans2); } return 0;}

最大报销额（wei=val浮点01背包）

​​#include #include using namespace std;const int N=3e6+10;int wei[N],dp[N];bool check(char ch){ if(ch=='A'||ch=='B'||ch=='C') return true; return false;}int main(){ //freopen("cin.txt","r",stdin); double q; int n,m; while(cin>>q>>n&&n){ int cnt=0; for(int i=0;i=wei[i];j--){ int t=dp[j-wei[i]]+wei[i]; //价格既有重量的性质又有价值的性质 dp[j]=t>dp[j]?t:dp[j]; } } printf("%.2lf\n",dp[qq]/100.0); } return 0;}

湫湫系列故事——减肥记I  (简单完全背包）

​​#include #include using namespace std;typedef long long LL;const LL N=105,M=1e5+10;LL n,V;LL wei[N],val[N],dp[M];LL work(){ memset(dp,0,sizeof(dp)); for(int i=0;it?dp[j]:t; } } return dp[V];}int main(){ //freopen("cin.txt","r",stdin); while(cin>>n){ for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。