完全背包专题训练(Pascal)

0-1背包问题与完全背包问题C++实现动态规划今天看了看背包九讲，⾃⼰写了下0-1背包和完全背包王晓东《计算机算法分析与设计》上⾯给出的C++实现⽐较繁琐，相⽐⽽⾔这个版本更加简明给出了测试数据0-1背包问题C++实现的最⼤价值Sample Input 3 34 57 9Sample Output 120 1 0 1*/#include<stdio.h>#include<string.h>int c[20][1000];//c[k][y]为只允许装前k 种物品，背包总重量不超过y 的最⼤价值int inumber[21][1000];//inumber[k][u]为只允许装前K 种物品，背包总重量不超过y 时得到最⼤价值时使⽤的背包的最⼤标号int w[21],p[21];int knapsack(int m,int n){ int i,j; for(i=1;i<n+1;i++) scanf("%d%d",&w[i],&p[i]); memset(c,0,sizeof(c)); memset(inumber,0,sizeo f(inumber)); for(j=1;j<m+1;j++){ c[1][j]=j/w[1]*p[1]; } for(i=1;i<n+1;i++){ for(j=1;j<m+1;j++){ if(j >= w[i]){ if(p[i]+c[i-1][j-w[i]]>=c[i-1][j]){ c[i][j]=p[i]+c[i-1][j-w[i]]; inumber[i][j]=i; } else{ c[i][j]=c[i-1][j]; inumber[i][j]=inumber[i-1][j]; } } else{ c[i][j]=c[i-1][j]; inumber[i][j]=inumber[i-1][j]; } }题的最⼤价值Sample Input10 42 13 34 51 9Sample Output900 0 0 10*/#include<stdio.h>#include<string.h>int c[20][1000];//c[k][y]为只允许装前k 种物品，背包总重量不超过y 的最⼤价值int inumber[21][1000];//inumber[k][u]为只允许装前K 种物品，h 背包总重量不超过y 时得到最⼤价值时使⽤的背包的最⼤标号int w[21],p[21];int knapsack(int m,int n){int i,j;for(i=1;i<n+1;i++)scanf("%d%d",&w[i],&p[i]);memset(c,0,sizeof(c));memset(inumber,0,sizeof(inumber));for(j=1;j<m+1;j++){c[1][j]=j/w[1]*p[1];}for(i=1;i<n+1;i++){for(j=1;j<m+1;j++){if(j >= w[i]){if(p[i]+c[i][j-w[i]]>=c[i-1][j]){//和0-1背包相⽐只是将c[i-1][j-w[i]]写成了c[i][j-w[i]]，因为完全背包问题中每件物品有⽆限个c[i][j]=p[i]+c[i][j-w[i]];inumber[i][j]=i;}else{c[i][j]=c[i-1][j];inumber[i][j]=inumber[i-1][j];}。

0-1背包问题详解⼆（完全背包问题）问题描述给定n种物品和⼀个背包。

物品i的重量是w(i),其价值为v(i),背包的容量为c(即最多能够装c重量的物品)。

这n种物品可以重复放置(这是与普通背包问题的不同之处)。

输⼊n=5,c=6.物品容量和价值分别为：2 62 36 55 44 6最后输出时：18问题求解：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}似乎利⽤上⾯那个公式就可以很好的求出解。

这⾥给出另外⼀组公式，该公式和上⽂的公式是⼀样的，只是第⼆个for语句的倒过来。

for i=1..Nfor v=0..Vf[v]=max{f[v],f[v-cost]+weight}为什么这样⼀改就可⾏呢？⾸先想想为什么上⽂中要按照v=V..0的逆序来循环。

这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推⽽来。

换句话说，这正是为了保证每件物品只选⼀次，保证在考虑“选⼊第i件物品”这件策略时，依据的是⼀个绝⽆已经选⼊第i件物品的⼦结果f[i-1][v-c[i]]。

⽽现在完全背包的特点恰是每种物品可选⽆限件，所以在考虑“加选⼀件第i种物品”这种策略时，却正需要⼀个可能已选⼊第i种物品的⼦结果f[i][vc[i]]，所以就可以并且必须采⽤v=0..V的顺序循环。

这就是这个简单的程序为何成⽴的道理。

1void compelteKnapsack(){2int c,n;3 cout<<"请输⼊最⼤容量,⼩于100"<<endl;4 cin>>c;5 cout<<"请输⼊背包个数"<<endl;6 cin>>n;7 cout<<"请输⼊各个背包重量和价值"<<endl;8for(int i=1;i<=n;i++){9 cin>>w[i]>>v[i];10 }11for(int i=0;i<=n;i++)12 p[i]=0;13for(int i=1;i<=n;i++)14for(int j=w[i];j<=c;j++)15 p[j]=max(p[j],p[j-w[i]]+v[i]);16 cout<<"结果是"<<p[c]<<endl;17 }View Code版权所有，欢迎转载，但是转载请注明出处：。

背包问题（3）：完全背包完全背包也是⼀种基本的背包问题模型，其基本特点是：每种物品可以放⽆限多次。

这个问题⾮常类似于0/1背包问题，所不同的是每种物品有⽆限件。

也就是从每种物品的⾓度考虑，与它相关的策略已并⾮取或不取两种，⽽是有取0件、取1件、取2件……等很多种。

完全背包问题的⼀般描述为：有N个物品，第i个物品的重量与价值分别为W[i]与P[i]。

背包容量为V，问在每个物品有⽆限个（物品必须保持完整）的情况下，如何让背包装⼊的物品具有更⼤的价值总和。

其⼀般解题思路为：令 f[i][j] 表⽰从编号1~i的物品中挑选任意数量的任意物品放⼊容量为j的背包中得到的最⼤价值，那么有f[i][j]=max { f[i−1][j]，f[i−1][j−k∗W[i]]+k∗P[i] } （0≤k && k∗W[i]≤j）编写代码时，可采⽤如下的循环。

for ( i=1;i<=N;i++) // 依次对每个物品进⾏处理for (j=1;j<=V;j++)for (k=1; k<=V/W[i];k++) // 物品最多只能放多少件{If (k*W[i]<=j)f[i][j]=max(f[i-1][j],f[i-1][j-k*W[i]]+k*P[i]);elsef[i][j]=f[i-1][j];}所求的最优值为f[N][V]。

同样完全背包也可以进⾏空间优化，将⼆维数组优化为⼀维数组，即f[j]=max { f[j]，f[j−k∗W[i]]+k∗P[i] } （0≤k && k∗W[i]≤j）编写代码时，⼀般采⽤如下的⼆重循环。

for (i=1;i<=N;i++) // 装⼊背包的物品个数为Nfor ( j=W[i];j<=V;j++) // 完全背包按由⼩到⼤顺序枚举重量f[j]=max(f[j],f[j-W[i]]+P[i]); // 状态转移所求的最优值为f[V]。

背包问题（⼀个以及⽆限个）题⽬说明：假設有⼀個背包的負重最多可達8公⽄，⽽希望在背包中裝⼊負重範圍內可得之總價物品，假設是⽔果好了，⽔果的編號、單價與重量如下所⽰：0李⼦4KG NT$45001蘋果5KG NT$57002橘⼦2KG NT$22503草莓1KG NT$11004甜⽠6KG NT$6700⾸先，是每种⽔果都只有⼀个的算法。

#include <stdio.h>#include <stdlib.h>int getMax(int fruitP[], int fruitW[], int form[][9], int fruitNum, int bagW){int i, j;for(i = 1; i <= fruitNum; i++){for(j = 1; j <= bagW; j++){if(j - fruitW[i] < 0){form[i][j] = form[i - 1][j];}else if(form[i - 1][j - fruitW[i]] + fruitP[i] > form[i - 1][j]){form[i][j] = form[i - 1][j - fruitW[i]] + fruitP[i];}else{form[i][j] = form[i - 1][j];}}}}print(int form[][9], int h, int l){int i, j;for(i = 0; i < l; i++) printf("%.5d ", i);printf("\n");for(i = 0; i < h; i++){for(j = 0; j < l; j++){printf("%.5d ", form[i][j]);}printf("\n");}}main(){int fruitP[6] = {0, 450, 570, 225, 110, 670};int fruitW[6] = {0, 4, 5, 2, 1, 6};int form[6][9] = {0};getMax(fruitP, fruitW, form, 5, 8);print(form, 6, 9);}如果⽔果是⽆限个则可以这么写：#include <stdio.h>#include <stdlib.h>int getMax(int fruitP[], int fruitW[], int form[][9], int fruitNum, int bagW){int i, j;for(i = 1; i <= fruitNum; i++){for(j = 1; j <= bagW; j++){if(j - fruitW[i] < 0){form[i][j] = form[i - 1][j];}else if(form[i - 1][j - fruitW[i]] + fruitP[i] > form[i - 1][j]){if(form[i - 1][j - fruitW[i]] + fruitP[i] > form[i][j - fruitW[i]] + fruitP[i])form[i][j] = form[i - 1][j - fruitW[i]] + fruitP[i];else form[i][j] = form[i][j - fruitW[i]] + fruitP[i];}else{if(form[i][j - fruitW[i]] + fruitP[i] < form[i - 1][j])form[i][j] = form[i - 1][j];else form[i][j] = form[i][j - fruitW[i]] + fruitP[i];}}}}print(int form[][9], int h, int l){int i, j;for(i = 0; i < l; i++) printf("%.5d ", i);printf("\n");for(i = 0; i < h; i++){for(j = 0; j < l; j++){printf("%.5d ", form[i][j]);}printf("\n");}}main(){int fruitP[6] = {0, 450, 570, 225, 110, 670};int fruitW[6] = {0, 4, 5, 2, 1, 6};int form[6][9] = {0};getMax(fruitP, fruitW, form, 5, 8);print(form, 6, 9);}⼀个和⽆限个的差别在于，在作⽐较的时候不仅跟上⼀⾏⽐较，还要跟当前⾏作⽐较，较⼤者置换即可。

完全背包问题（LeetCode第322、518题）题⽬：518题给定不同⾯额的硬币和⼀个总⾦额。

写出函数来计算可以凑成总⾦额的硬币组合数。

假设每⼀种⾯额的硬币有⽆限个。

分析：对于这种动态规划问题，我们必须弄清楚这⼏个问题：状态数组的含义、状态转移⽅程、边界条件以及状态数组索引的选择范围。

⾸先我们来定义⼀个状态数组，根据题⽬要求我们知道最终的⽬标是要求那么⼦问题就是在前i种硬币的选择范围下，凑成当前所要求的⾦额的组合数⽬。

所以状态转移数组就是⼀个⼆维数组：dp[i][j]。

dp[i][j]：前i中硬币，在总⾦额为j的情况下，硬币的组合数。

然后来分析状态转移⽅程： 对于当前访问的⾦币coin： 如果 coin > j，那么当前⾦币不能放⼊组合，所以dp[i][j] = dp[i-1][j] 如果 coin <= j，那么当前⾦币可以考虑放⼊组合，⽽且放⼊⼏个也是需要考虑的，所以因为我们要求的是组合数，所以任何组合都要考虑，所以dp[i][j] = sum(dp[i-1][j-k*coin]),k * coin <= j边界条件： （1）有⾦币，但是总额为0时，那么组合数应为1， （2）⽆⾦币，也⽆总额，组合数也为1； （3）总额⼤于0，⾦币为⽆，那么没有组合能够凑成总额，所以组合数为0所以最终的实现代码如下：public int change(int amount, int[] coins) {if (amount>0 && coins.length==0)return 0;int n = coins.length;int[][] dp = new int[n+1][amount+1];dp[0][0] = 1;for (int i = 1; i <= n; i++) {for (int j = 0; j <= amount; j++) {if (coins[i-1] > j)dp[i][j] = dp[i-1][j];else {for (int k = 0; k * coins[i-1]<= j; k++) {dp[i][j] += dp[i-1][j-k*coins[i-1]];}}}}return dp[n][amount];}优化⼀：进⼀步分析dp[i][j],发现它的值依赖于两种情况，对于第i个⾦币，是否加⼊背包？ （1）不加⼊，那么dp[i][j] = dp[i-1][j]; （2）加⼊，那么当前背包容量变成了j-coin,但是由于⾦币是⽆限的所以对于硬币的选择范围依旧是前i个⾦币。

1、0/1背包
【问题描述】
一个旅行者有一个最多能装m公斤物品的背包，现在有n件物品，它们的重量分别是w1,w2,…,wn,它们的价值分别为c1,c2,…cn。

若每种物品只有一件，求旅行者能获得的最大总价值。

【输入格式】
第一行：两个整数m（背包容量，m≤200）和n（物品数量，n≤30）；
第二~n+1行：每行两个整数wi,ci,表示每个物品的重量和价值。

【输出格式】
一个数据，表示最大总价值。

【输入样例】
10 4
2 1
3 3
4 5
7 9
【输出样例】
12
2、完全背包问题
【问题描述】
设有n中物品，每种物品有一个重量及一个价值。

但每种物品的数量是无限的，同时有一个背包，最大载重量为m，今从n种物品中选取若干件（同一物品可以多次选取），使其重量的和小于等于m，而价值的和为最大。

【输入格式】
第一行：两个整数，m（背包容量，m≤200）和（物品数量，n≤30）；
第二~n+1行：每行两个整数wi，ui，表示每个物品的重量和价值。

【输出格式】
仅一行，一个数，表示最大总价值。

【输入样例】
10 4
2 1
3 3
4 5
7 9
【输出样例】
max=12。

背包问题：0-1背包、完全背包和多重背包背包问题泛指以下这⼀种问题：给定⼀组有固定价值和固定重量的物品，以及⼀个已知最⼤承重量的背包，求在不超过背包最⼤承重量的前提下，能放进背包⾥⾯的物品的最⼤总价值。

这⼀类问题是典型的使⽤动态规划解决的问题，我们可以把背包问题分成3种不同的⼦问题：0-1背包问题、完全背包和多重背包问题。

下⾯对这三种问题分别进⾏讨论。

1.0-1背包问题0-1背包问题是指每⼀种物品都只有⼀件，可以选择放或者不放。

现在假设有n件物品，背包承重为m。

对于这种问题，我们可以采⽤⼀个⼆维数组去解决：f[i][j]，其中i代表加⼊背包的是前i件物品，j表⽰背包的承重，f[i][j]表⽰当前状态下能放进背包⾥⾯的物品的最⼤总价值。

那么，f[n][m]就是我们的最终结果了。

采⽤动态规划，必须要知道初始状态和状态转移⽅程。

初始状态很容易就能知道，那么状态转移⽅程如何求呢？对于⼀件物品，我们有放进或者不放进背包两种选择：（1）假如我们放进背包，f[i][j] = f[i - 1][j - weight[i]] + value[i]，这⾥的f[i - 1][j - weight[i]] + value[i]应该这么理解：在没放这件物品之前的状态值加上要放进去这件物品的价值。

⽽对于f[i - 1][j - weight[i]]这部分，i - 1很容易理解，关键是 j - weight[i]这⾥，我们要明⽩：要把这件物品放进背包，就得在背包⾥⾯预留这⼀部分空间。

（2）假如我们不放进背包，f[i][j] = f[i - 1][j]，这个很容易理解。

因此，我们的状态转移⽅程就是：f[i][j] = max(f[i][j] = f[i - 1][j] , f[i - 1][j - weight[i]] + value[i])当然，还有⼀种特殊的情况，就是背包放不下当前这⼀件物品，这种情况下f[i][j] = f[i - 1][j]。