0-1 多重 组合背包的自学之路(不断更新中)

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

它有两种情况：

第一种是第i件不放进去，这时所得价值为:f[i-1][v]

第二种是第i件放进去，这时所得价值为：f[i-1][v-c[i]]+w[i]

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

最后比较第一种与第二种所得价值的大小，哪种相对大，f[i][v]的值就是哪种。

（这是基础，要理解！）

这里是用二位数组存储的，可以把空间优化，用一位数组存储。

用f[0..v]表示，f[v]表示把前i件物品放入容量为v的背包里得到的价值。把i从1~n(n件)循环后，最后f[v]表示所求最大值。

*这里f[v]就相当于二位数组的f[i][v]。那么，如何得到f[i-1][v]和f[i-1][v-c[i]]+w[i]？（重点！思考）
首先要知道，我们是通过i从1到n的循环来依次表示前i件物品存入的状态。即：for i=1..N
现在思考如何能在是f[v]表示当前状态是容量为v的背包所得价值，而又使f[v]和f[v-c[i]]+w[i]标签前一状态的价值？

逆序！

这就是关键！

分析上面的代码：当内循环是逆序时，就可以保证后一个f[v]和f[v-c[i]]+w[i]是前一状态的！
这里给大家一组测试数据：

测试数据：
10,3
3,4
4,5
5,6

#include<cstdio>
#include<cstring>
int f[1024];
int w[1024];
int c[1024];
int main()
{int t;scanf("%d",&t);while(t--){int n,m;scanf("%d %d",&n,&m);for(int i=0;i<n;i++) scanf("%d",&c[i]);for(int i=0;i<n;i++) scanf("%d",&w[i]);memset(f,0,sizeof(f));for(int i=0;i<n;i++){for(int j=m;j>=w[i];j--){if(f[j-w[i]]+c[i]>f[j])//定义为装入c[i]物品的第[j-w[i]]位置，依次刷新f[j]=f[j-w[i]]+c[i];//恰巧此时f[j-w[i]]为上一状态，所以可以拿来使用，}                           //所以说就是在每一个质量位上一直在累加}printf("%d\n",f[m]);}return  0；
}

02完全背包：

完全背包(CompletePack): 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

完全背包按其思路仍然可以用一个二维数组来写出：

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

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

伪代码如下：

顺序！

想必大家看出了和01背包的区别，这里的内循环是顺序的，而01背包是逆序的。
现在关键的是考虑：为何完全背包可以这么写？

在次我们先来回忆下，01背包逆序的原因？是为了是max中的两项是前一状态值，这就对了。
那么这里，我们顺序写，这里的max中的两项当然就是当前状态的值了，为何？
因为每种背包都是无限的。当我们把i从1到N循环时，f[v]表示容量为v在前i种背包时所得的价值，这里我们要添加的不是前一个背包，而是当前背包。所以我们要考虑的当然是当前状态。

#include<cstdio>
#include<cstring>
int f[1024];
int w[1024];
int c[1024];
int main()
{int t;scanf("%d",&t);while(t--){int n,m;scanf("%d %d",&n,&m);for(int i=0;i<n;i++) scanf("%d",&c[i]);for(int i=0;i<n;i++) scanf("%d",&w[i]);memset(f,0,sizeof(f));//		for(int i=0;i<n;i++)
//		{
//			for(int j=m;j>=w[i];j--)
//			{
//				if(f[j-w[i]]+c[i]>f[j])
//				f[j]=f[j-w[i]]+c[i];
//			}
//		}for(int i=0;i<n;i++){for(int j=w[i];j<=m;j++){if(f[j-w[i]]+c[i]>f[j])//作为先序首先无限对高端值钱的添加f[j]=f[j-w[i]]+c[i];//就是对0-1背包的改版}}printf("%d\n",f[m]);}}

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
int dp[100005];
int w[1000];
int c[1000]; 
int main(){int n,m,a,b,cc,cnt;while(cin >> n >> m) //{cnt=1;memset(dp,0,sizeof(dp)); memset(c,0,sizeof(c));memset(w,0,sizeof(w));for(int i=1;i<=n;i++){cin >> a >> b >> cc;       //a个东西质量为b,jiazhiwei cc for(int j=1;j<=a;j*=2){w[cnt]=j*b;c[cnt++]=cc*j;a-=j;}if(a>0){w[cnt]=a*b;c[cnt++]=cc*a;}}dp[0]=0; for(int i=1;i<=cnt;i++)for(int j=m;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+c[i]);cout << dp[m] <<endl;}return 0;
}