首页 > 代码库 > 8月4ACM集训之---------背包问题
8月4ACM集训之---------背包问题
好想吐槽一下，每一个专题两天，还要努力数排名，对我这样一个比较笨又不是很勤奋的人来说，真心有点吃力，好多东西都只能做到一知半解————要加油了---不然会被鄙视的的
背包——通俗理解就是将背包装满的问题，其要求一般是使其价值最大
01背包：
有N件物品和一个重量为M的背包。（每种物品均只有一件）第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大。
每个物体都有两个属性，value和weight,而背包则有size，用V[i, j]用来表示从前 i 项{u1......ui}（背包中的物品）中取出来的装入体积为size的背包的最大价值。
V[i, j] = 0 若i = 0 或 j = 0;
V[i, j] = V[i - 1, j] 若j < ui.weight;(当物品的重量大于背包承重时,就不巴物品放在里面)
V[i, j] = max{V[i - 1, j], V[i - 1, j - ui.weight] + ui.value} 若i > 0并且j >= ui.weight
简化后的模板未：f[v]=max{f[v],f[v-c]+w}（前i件武平放入容积为v的背包中可获得的最大价值）
完全背包：
每种物品可以放无限放
多重背包问题：
每种物品有一个固定的次数上限
二维费用的背包问题：
二维费用的背包问题是指对于每件物品，具有两种不同的费用，选择这件物品必须同时付出这两种代价，对于每种代价都有一个可付出的最大值（背包容量），求选择物品可以得到最大的价值。设第i件物品所需的两种代价分别为v[i]和u[i]，两种代价可付出的最大值（两种背包容量）分别为V和U，物品的价值为w[i]。
例：杭电acm 2602
#include<stdio.h>#include<string.h>#include<iostream>using namespace std;int max(int a,int b){ return a>b?a:b;}int main(){ int t,n,m,dp[10001],i,j; int a[10000],b[10000]; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } for(i=1;i<=n;i++) { scanf("%d",&b[i]); } for(i=1;i<=n;i++) { for(j=m;j>=b[i];j--) { dp[j]=max(dp[j],dp[j-b[i]]+a[i]); } } cout<<dp[m]<<endl; } return 0;}
杭电 对布的裁剪问题
#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;struct node{ int val,wei;} a[155];int dp[155][155];int main(){ int n,m,k,s,x,y,z,i; while(~scanf("%d%d%d%d",&n,&m,&k,&s)) { for(i = 1; i<=k; i++) scanf("%d%d",&a[i].val,&a[i].wei); memset(dp,0,sizeof(dp)); for(x = 1; x<=m; x++) { for(y = 1; y<=k; y++) { for(z = 1; z<=s; z++) { int cnt = 1; while(cnt*a[y].wei<=x && cnt<=z) { dp[x][z] = max(dp[x][z],dp[x-cnt*a[y].wei][z-cnt]+cnt*a[y].val); cnt++; } } } if(dp[x][s]>=n) break; } if(x>m) printf("-1\n"); else printf("%d\n",m-x); } return 0;}
#include <stdio.h>#include <algorithm>#include <string.h>using namespace std;struct node{ int x,y,v;}a[20];int dp[1005][1005];int main(){ int i,j,k,n,X,Y,t; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&X,&Y); for(i = 0;i<n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v); memset(dp,0,sizeof(dp)); for(i = 0;i<=X;i++)//二维背包 { for(j = 0;j<=Y;j++) { for(k = 0;k<n;k++) { if(i>=a[k].x && j>=a[k].y) dp[i][j] = max(dp[i][j],max((dp[i-a[k].x][j]+dp[a[k].x][j-a[k].y]),(dp[i][j-a[k].y]+dp[i-a[k].x][a[k].y]))+a[k].v); if(i>=a[k].y && j>=a[k].x) dp[i][j] = max(dp[i][j],max((dp[i-a[k].y][j]+dp[a[k].y][j-a[k].x]),(dp[i][j-a[k].x]+dp[i-a[k].y][a[k].x]))+a[k].v); } } } printf("%d\n",dp[X][Y]); } return 0;}
//求最小价值
#include<stdio.h>#include<string.h>#include"cstdio"#include<iostream>using namespace std;#define max 10000000;struct node{ int value; int weight;}a[10005];int dp[10000];int main(){ int t,n,m,m1,m2,i,j; scanf("%d",&t); while(t--) { scanf("%d%d",&m1,&m2); scanf("%d",&n); m=m2-m1; for(i=0;i<=m;i++) dp[i]=10000000; dp[0]=0; for(i=0;i<n;i++) { scanf("%d%d",&a[i].value,&a[i].weight); } for(i=0;i<n;i++) { for(j=a[i].weight;j<=m;j++) { if(dp[j]>dp[j-a[i].weight]+a[i].value) dp[j]=dp[j-a[i].weight]+a[i].value; } } if(dp[m]==10000000) printf("This is impossible.\n"); else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[m]); } return 0;}