# 背包问题总结 原

GenHao2

### 01背包

tab[i][j] = max(tab[i-1][j-weight[i]]+value[i],tab[i-1][j]) ({i,j|0<i<=n,0<=j<=total})

``````for i=[0,n)
for(j=totle;j>=weight[i]; j--)
tab[j] = max(tab[j-weight[i]]+value[i],tab[j])
/* print tab[0][total] */``````

### 完全背包

tab[j] = max(tab[j-weight[i]]+value[i],tab[j]);({i,j|0<i<=n,0<=j<=total})

``````for i=[0,n)
for(j=weight[i]; j<=total; j++)
tab[j] = max(tab[j-weight[i]]+value[i],tab[j])
/*    print tab[0][total]    */``````

### 多重背包

``````for i=[0,n)
/*    将count数组清零        */
for(j=weight[i]; j<=total; j++)
if    count[j-weight[i]]<amout[i]
tab[j] = max(tab[j-weight[i]]+value[i],tab[j]);
if    tab[j]=tab[j-weight[i]]+value[i]   //    决定放入i是较优解
count[i] = count[j-weight[i]] + 1
else    if    tab[j]=0       //    防止装第1个物品和装其他物品的情况
tab[j] = tab[j-1],count[j] = count[j-1]
else    count[j] = count[j-1]
/*    print tab[0][total]    */``````

### 相关例题

HDU2546：饭卡
http://acm.hdu.edu.cn/showproblem.php?pid=2546(01背包)

```#include <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
int n;
while(~scanf("%d",&n),n)
{
int i,price[2013]= {0},dp[2013] = {0};
for(i = 1; i<=n; i++)
scanf("%d",&price[i]);
sort(price+1,price+1+n);
int MAX=price[n];
int j,m;
scanf("%d",&m);
if(m<5)//低于5元不能购买
{
printf("%d\n",m);
continue;
}
m-=5;//取出5元用于购买最贵的物品
for(i = 1; i<n; i++)//01背包
{
for(j = m;j>=price[i];j--)
{
dp[j] = max(dp[j],dp[j-price[i]]+price[i]);
}
}
printf("%d\n",m+5-dp[m]-MAX);
}
return 0;
}```

HDU 4508湫湫系列故事——减肥记I

```#include<iostream>
#include<algorithm>
using namespace std;
int max(int a,int b)
{
if(a>b) return a;
else    return b;
}
int main()
{
int n,m;
int a[100005],b[100005],c[100005];
while(scanf("%d",&n)!=EOF)
{
memset(c,0,sizeof(c));
for(int i=0;i<n;i++)
scanf("%d%d",&a[i],&b[i]);
scanf("%d",&m);
for(int j=0;j<n;j++)
{
for(int k=b[j];k<=m;k++)
{
c[k]=max(c[k-b[j]]+a[j],c[k]);
}
}
printf("%d\n",c[m]);
}
return 0;
}```

hdu 2602 Bone Collector

```#include<iostream>
#include<algorithm>
using namespace std;
int max(int a,int b)
{
if(a>b) return a;
else    return b;
}
int main()
{
int T,N,V;
int i,j,k;
int v[1005],w[1005],c[1005];
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&N,&V);
for(i=0;i<N;i++)
scanf("%d",&v[i]);
for(i=0;i<N;i++)
scanf("%d",&w[i]);
memset(c,0,sizeof(c));
for(i=0;i<N;i++)
{
for(j=V;j>=w[i];j--)
{
c[j]=max(c[j],c[j-w[i]]+v[i]);
}
}
printf("%d\n",c[V]);
}
return 0;
}```

HDU 1203I NEED A OFFER!

```#include <iostream>
#include<algorithm>
using namespace std;
const int N=10000+1;
int a[N];
float b[N],f[N];
int main(int argc, char *argv[])
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF&&m+n)
{
memset(f,0,sizeof(f));
for(int i=0;i<m;i++)
cin>>a[i]>>b[i];
for(int i=1;i<m;i++)
{
for(int j=n;j>a[i];j--)
{
f[j]=max(f[j],1-(1-f[j-a[i]])*(1-b[i]));
}
}
printf("%.1f%%\n",f[n]*100);
}
return 0;
}
//01背包问题

f[j] = max{f[j],1-(1-f[j-c[i]])*(1-w[i])}
max中的f[j]表示分析完上一所学校之后j万元能够获取的最大被录取概率

max中的(1-(1-f[j-c[i]])*(1-w[i]))表示选择了i校之后被录取的概率。
f[j-c[i]]:除去i校的申请费之后，用剩余的钱所获取的被录取最大概率。```
```#include <stdio.h>
#include <string.h>
int max(int a,int b)
{
return  a>b?a:b;
}
int main(int argc, char *argv[])
{
int i,j,m,n;
int dp[10001];
int a[3]={150,200,350};
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
memset(dp,0,sizeof(dp));
for(i=0;i<3;i++)
{
for(j=a[i];j<=m;j++)
{
dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
}
}
printf("%d\n",m-dp[m]);
}
return 0;
}
//完全背包问题```
```#include <iostream>
#include <cstring>
using namespace std;
int dp[1001], v[1000], p[1000];
inline int max(int a, int b) { return a>b?a:b;  }
int main()
{ int c;
scanf("%d", &c);
while (c--) {
int n, V, i, j;
scanf("%d %d", &n, &V);
for (i=0; i<n; i++)
scanf("%d", &p[i]);
for (i=0; i<n; i++)
scanf("%d", &v[i]);
memset(dp, 0, sizeof(dp));
for (i=0; i<n; i++)
for (j=V; j>=v[i]; j--)
dp[j] = max(dp[j], dp[j-v[i]] + p[i]);
printf("%d\n", dp[V]);
}
}
//01背包问题```

01背包（ZeroOnePack）: 有N件物品和一个容量为V的背包。（每种物品均只有一件）第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

——————————————————————————————————————————————————————————–：

01背包（ZeroOnePack）: 有N件物品和一个容量为V的背包。（每种物品均只有一件）第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

## f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

``````把这个过程理解下：在前i件物品放进容量v的背包时，

（第二种是什么意思？就是如果第i件放进去，那么在容量v-c[i]里就要放进前i-1件物品）

（这是基础，要理解！）

*这里f[v]就相当于二位数组的f[i][v]。那么，如何得到f[i-1][v]和f[i-1][v-c[i]]+w[i]？（重点！思考）

# 逆序！

1for i=1..N
2   for v=V..0
3        f[v]=max{f[v],f[v-c[i]]+w[i]};
4

10,3
3,4
4,5
5,6

C[v]从物品i=1开始，循环到物品3，期间，每次逆序得到容量v在前i件物品时可以得到的最大值。（请在草稿纸上自己画一画）

——————————————————————————————————————————————————————————–

## `f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}`

`同样可以转换成一维数组来表示：`

`伪代码如下：`

for i=1..N
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]}

# 顺序！

（分析代码也是学习算法的一种途径，有时并不一定要看算法分析，结合题目反而更容易理解。）

——————————————————————————————————————————————————————————–

## `f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}`

### GenHao2

1、两种重要算法思想： 动态规划，贪心算法 2、动态规划： 基本原理：动态规划英文名dynamic programming。其中pogramming指的是表格法，而非编写计算机程序。因此，可以初步得出动态规划的基...

thoresa
2015/05/18
0
0

07/31
0
0

0-1 背包问题：给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。 问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？ 分析一波，面对每个物品，我...

xp731574722
2017/04/25
0
0

TOTOTO_TOTO
2013/12/15
0
0

Playboy002
2015/07/17
42
0

6分钟前
1
0
ali oss util demo

package com.example.demo;import com.aliyun.oss.OSSClient;import com.aliyun.oss.common.utils.BinaryUtil;import com.aliyun.oss.model.*;import org.slf4j.Logger;import o......

8分钟前
1
0
Windows系统中eclipse修改字体为Courier New

anlve
8分钟前
1
0

hexo有什么用？ hexo 可以把md文件生成html静态网页。 hexo官网：https://hexo.io/zh-cn/ 本地安装hexo。 npm install -g hexo-cli#生成blog（名字任意）文件夹，并且在这个文件夹里面初始化...

8分钟前
1
0
RabbitMQ+PHP 教程四（Routing）用yii2测试通过

hansonwong
13分钟前
2
0