完全背包和01背包的区别在于完全背包里的每一件物品的数量有无数个。
模板
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= v; ++j) {
if (c[i] <= j)
f[i][j] = max(f[i - 1][j],f[i][j - c[i]] + v[i]);
else
f[i][j] = f[i - 1][j];
}
}
与01背包类似的模板
for (int i = 1; i <= n; ++i) {
for (int j = w[i]; j <= v; ++j) {
f[j] = max(f[j], f[j - c[i]] + v[i]);
}
}
模板题
极度怀疑这个题目有错看，结果应该是10
//#include <bits/stdc++.h>
int dp[101][101],w[101],v[101];
//方法一
int main(){
freopen("data","r",stdin);
int n,W;
cin>>n;
for(int i=0;i<n;i++)
cin>>w[i]>>v[i];
cin>>W;
for(int i=0;i<n;i++)
for(int j=0;j<=W;j++)
if(j<w[i])
dp[i+1][j]=dp[i][j];
else{
dp[i+1][j]=max(dp[i-1][j],dp[i+1][j-w[i]]+v[i]);
}
cout<<dp[n][W];
return 0;
}
//方法二
for(int i=0;i<n;i++)
for(int j=w[i];j<=W;j++)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
cout<<dp[W];
一大波例题来啦
Piggy-Bank
#include <bits/stdc++.h>
using namespace std;
long long int dp[1000001],w[10000001],v[1000001];
int main(){
freopen("data","r",stdin);
long long int t,weight,W,n;
scanf("%lld",&t);
while(t--){
//dp[0]=0;
scanf("%lld%lld",&weight,&W);
W-=weight;
//切记，这里不能把dp[0]也设置成inf！
for(int i=1;i<=W;i++) dp[i]=1000000000;
scanf("%lld",&n);
for(int i=0;i<n;i++)
scanf("%lld%lld",&v[i],&w[i]);
for(int i=0;i<n;i++)
for(int j=w[i];j<=W;j++)
dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
if(dp[W]==1000000000)
cout<<"This is impossible."<<endl;
else
printf("The minimum amount of money in the piggy-bank is %lld.\n",dp[W]);
}
return 0;
}
Robberies
这道题很有意思：题目中给定价值和被抓几率，但是被抓几率不可以用乘积来组合计算，举个例子，比如第一个银行3%被抓几率，第二个5%被抓几率，那么乘起来会变成0.15%，抢的越多，被抓几率却越小了，显然不对，因此要转换成不被抓几率，上述例子则变为第一家97%不被抓，第二家95%不被抓，乘起来就是92.15%，抢的越多，不被抓的几率越来越小即被抓几率越来越大，这样才是符合常理的。
因为几率都是小于1的，所以相乘一定会减小，而强的银行越多，被抓率不可能减少//如果是这样，大家都去抢银行了~~
//#include <bits/stdc++.h>
using namespace std;
#define eps 0.000000000001
double w[10100],W,dp[10100];
int a[10100],n;
int t;
//w[i]是被抓几率，然后转成逃跑几率
int main(){
// freopen("data","r",stdin);
cin>>t;
while(t--){
int sum=0;
memset(dp,0,sizeof(dp));
scanf("%lf%d",&W,&n);
//把它变成逃跑几率
W=1-W;
dp[0]=1;//你不抢银行你就不用被抓咯
for(int i=0;i<n;i++)
{
scanf("%d%lf",&a[i],&w[i]);
w[i]=1-w[i];
sum+=a[i];
}
for(int i=0;i<n;i++)
//钱数从最多开始循环
for(int j=sum;j>=a[i];j--)
dp[j]=max(dp[j],dp[j-a[i]]*w[i]);
for(int i=sum;i>=0;i--){
if(dp[i]>W){
printf("%d\n",i);
break;
}
}
}
return 0;
}
多重背包
例题
珍惜现在，感恩生活
拆分那里刚开始是没有搞懂的，然后看了师兄发的文件，又试着将过程输出了一下，才明白拆分的含义，比如说这道题有四袋米，我可以把它拆成三分，一分是一袋米，一份是两袋米，最后一份还是一袋米（通过补充来计算），将他们存入一个新的数组里面，最后再对这个新的数组进行01背包就可以了嘛~
//#include <bits/stdc++.h>
using namespace std;
int max(int x,int y){
return x>y?x:y;
}
struct E
{
int w; //体积
int v; //重量
} lis[2001];
int dp[101];
int main()
{
int T,n,m;
int p,h,k;
int i,j;
int index,c;
cin>>T;
while(T--){
scanf("%d%d",&n,&m); //n表示容量，m表示种类
index = 0; //拆分后物品总数
for( i=1; i<=m; i++)
{
c = 1;
scanf("%d%d%d",&p,&h,&k); //p表示价格，h表示重量，k表示大米袋数。
//这里开始拆分
while( k-c>0)
{
k -= c;
lis[++index].w = c*p;
lis[index].v = c*h;
c *= 2;
}
lis[++index].w = p*k; //补充不足指数的差值
lis[index].v = h*k;
}
for( i=0; i<=n; i++) dp[i]=0;
for( i=1; i<=index; i++) //对拆分后的物品进行0-1背包
{
for( j=n; j>=lis[i].w; j--)
dp[j] = max( dp[j],dp[j-lis[i].w]+lis[i].v);
}
printf("%d\n",dp[n]);
}
return 0;
}
Coins
其实刚开始看到这个问题时，想到的时完全背包，但是对于一个菜鸟来说，不知道怎么打，然后看了一些大佬的代码，才有了头绪---说是双线背包~
这里的dp起到标记的作用，sum[j]是用来记录每j元需要多少个硬币，ans是用来记录次数。
解法一
//#include <bits/stdc++.h>
using namespace std;
int dp[100001],n,m,v[101],w[101],sum[100001];
int main()
{
while(cin>>n>>m&&m&&n){
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
cin>>v[i];
for(int i=0;i<n;i++)
cin>>w[i];
dp[0]=1;
int ans=0;
for(int i=0;i<n;i++){
memset(sum,0,sizeof(sum));
for(int j=v[i];j<=m;j++){
//这里进行筛选
//sum[j]表示当前物品填充j大小的包需要至少使用多少个.
if(!dp[j]&&dp[j-v[i]]&&sum[j-v[i]]<w[i]){
dp[j]=1;
sum[j]=sum[j-v[i]]+1;
ans++;
}
}
}
cout<<ans<<endl;
}
return 0;
}
解法二（多重部分和）
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
int dp[100001];
int A[100001],C[1001];
int a[4]={0,1,2,5};
int m;
int n,K=15000;
int main()
{
while(cin>>n>>m&&(n!=0||m!=0)){
memset(dp,-1,sizeof(dp));
dp[0]=0;
for(int i=0;i<n;i++)
cin>>A[i];
for(int i=0;i<n;i++)
cin>>C[i];
for(int i=0;i<n;i++)
for(int j=0;j<=m;j++){
if(dp[j]>=0)
dp[j]=C[i];
else if(A[i]>j||dp[j-A[i]]<=0)
dp[j]=-1;
else
dp[j]=dp[j-A[i]]-1;
}
int res=0;
for(int i=1;i<=m;i++){
if(dp[i]>=0)
res++;
}
cout<<res<<endl;
}
return 0;
}
Cash Machine
这道题和第一道例题很像,只不过没有用结构体每一步都是按照模板来滴
//#include <bits/stdc++.h>
using namespace std;
int dp[100001],n,m,v[101],w[101],sum[100001];
int max(int x,int y){
return x>y?x:y;
}
int main()
{
freopen("data","r",stdin);
int cash,num,denomination;
while(cin>>cash){
int index=0;
memset(v,0,sizeof(v));
cin>>n;
for(int i=0;i<n;i++){
cin>>num>>denomination;//种类和面值
//接着将种类进行拆分
int k=1;
while(num-k>0){
num-=k;
v[++index]=k*denomination;
//w[i]=k*? 因为这里没有类似质量的变量，所以不需要这一步啦
k*=2;
}
v[++index]=num*denomination;
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=index;i++)
for(int j=cash;j>=v[i];j--){//可以试一下不倒过来的
dp[j]=max(dp[j],dp[j-v[i]]+v[i]);
}
int ans=0;
for(int i=0;i<=cash;i++)
ans=max(ans,dp[i]);
cout<<ans<<endl;
}
return 0;
}
Dividing
原本交了代码却wa了，幸亏没有放弃自己的代码，最后发现是忘记将dp归零了（捂脸
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
//#include <cstdlib>
#include <cstring>
using namespace std;
int dp[100001],n,m,v[101],w[101],num[100001],nv[101],nw[101];
int max(int x,int y){
return x>y?x:y;
}
int main()
{
int m=1;
//freopen("data","r",stdin);
while(cin>>w[1]>>w[2]>>w[3]>>w[4]>>w[5]>>w[6]){
int sum=0,index=0;
for(int i=1;i<=6;i++){
int k=1;
sum+=i*w[i];
while(w[i]>k){
nw[++index]=k*i;
w[i]-=k;
k*=2;
}
nw[++index]=w[i]*i;
}
if(sum==0)
return 0;
cout<<"Collection #"<<m++<<":"<<endl;
if(sum%2){
cout<<"Can't be divided."<<endl<<endl;
}else{
memset(dp,0,sizeof(dp));
sum/=2;
for(int i=1;i<=index;i++){
for(int j=sum;j>=nw[i];j--)
dp[j]=max(dp[j],dp[j-nw[i]]+nw[i]);
}
if(dp[sum]==sum)
cout<<"Can be divided."<<endl<<endl;
else
cout<<"Can't be divided."<<endl<<endl;
}
}
return 0;
}
