参考《挑战算法设计竞赛》p.58
https://www.cnblogs.com/Ymir-TaoMee/p/9419377.html
完全背包问题：
问题描述：有n种重量和价值分别为wi，vi的物品，从这些物品中挑选总重量不超过W的物品，求出挑选物品价值总和的最大值，在这里，每种物品可以挑选任意多件。
input:
3
7
3 4
4 5
2 3
output:
10 ( 0号物品选1个，2号物品选2个)
这次同一种类的物品可以选择任意多件了，尝试着写出递推关系：
dp[i+1][j] := 从前i+1种(编号0到i)物品中挑选总重量不超过j时总价值的最大值.
dp[0][j]=0(前面0种)
dp[i+1][j]=max{dp[i][j-k*w[i]]+k*v[i]|k≥0}
c++版本解法：
#include <iostream>
#include <cstring>
using namespace std;
int n,W;
int * w;
int * v;
int **dp;
int max(int x, int y)
{
if (x>y) return x;
return y;
}
int main()
{
cin >> n >> W;
w = new int[n];
v = new int[n];
for (int i=0; i<n; i++)
{
cin >> w[i] >>v[i];
}
dp = new int*[n+1];
for (int i=0; i<=n; i++)
{
dp[i] = new int[W+1];
memset(dp[i],0,sizeof(int)*(W+1));
}
for (int i=0; i<n; i++)
{
for (int j=0; j<=W; j++)
{
for (int k=0; k*w[i]<=j; k++)
{
dp[i+1][j] = max(dp[i+1][j],dp[i][j-k*w[i]]+k*v[i]);
}
}
}
cout << dp[n][W] << endl;
}
Java版本解法：
package 记忆化搜索;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int W=sc.nextInt();
int []w=new int[n];
int []v=new int[n];
for (int i = 0; i < v.length; i++) {
w[i]=sc.nextInt();
v[i]=sc.nextInt();
}
int dp[][]=new int[n+1][W+1];
for (int i=0; i<n; i++)
{
for (int j=0; j<=W; j++)
{
for (int k=0; k*w[i]<=j; k++)
{
dp[i+1][j] = Math.max(dp[i+1][j],dp[i][j-k*w[i]]+k*v[i]);
}
}
}
System.out.println(dp[n][W]);
}
}
上面的程序是三重循环的，关于k的循环最坏可能从0到W，所以这个算法的复杂度为O(nW2),这样并不够好
我们来找一找这个算法中多余的计算(已经知道结果的计算)，在dp[i+1][j]的计算中选择k(k≥1)个的情况，与在dp[i+1][j-w[i]]的计算中选择k-1个情况是相同的，所以
dp[i+1][j]的递推中k≥1部分的计算已经在dp[i+1][j-w[i]]的计算中完成了：
dp[i+1][j]
= max{dp[i][j-k*w[i]]+k*v[i]|k≥0}
= max(dp[i][j],max{dp[i][j-k*w[i]]+k*v[i]|k≥1})
= max(dp[i][j],max{dp[i][(j-w[i])-k*w[i]]+k*v[i]|k≥0}+v[i])
= max(dp[i][j],dp[i+1][j-w[i]]+v[i])
即：dp[i+1][j] = max(dp[i][j],dp[i+1][j-w[i]]+v[i])
这样处理之后，就不需要关于k的循环了，现在的复杂度为O(nW)
C++版本解法：
#include <iostream>
#include <cstring>
using namespace std;
int n,W;
int * w;
int * v;
int **dp;
int max(int x, int y)
{
if (x>y) return x;
return y;
}
int main()
{
cin >> n >> W;
w = new int[n];
v = new int[n];
for (int i=0; i<n; i++)
{
cin >> w[i] >>v[i];
}
dp = new int*[n+1];
for (int i=0; i<=n; i++)
{
dp[i] = new int[W+1];
memset(dp[i],0,sizeof(int)*(W+1));
}
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][j],dp[i+1][j-w[i]]+v[i]);
}
}
cout << dp[n][W] << endl;
}
JAVA版本解法：
package 记忆化搜索;
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int W=sc.nextInt();
int []w=new int[n];
int []v=new int[n];
for (int i = 0; i < v.length; i++) {
w[i]=sc.nextInt();
v[i]=sc.nextInt();
}
int dp[][]=new int[n+1][W+1];
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] = Math.max(dp[i][j],dp[i+1][j-w[i]]+v[i]);
}
}
System.out.println(dp[n][W]);
}
}
利用滚动数组解决两种背包问题
0-1背包问题
C++版本解法：
#include <iostream>
#include <cstring>
using namespace std;
int n,W;
int * w;
int * v;
int *dp;
int max(int x, int y)
{
if (x>y) return x;
return y;
}
int main()
{
cin >> n >> W;
w = new int[n];
v = new int[n];
for (int i=0; i<n; i++)
{
cin >> w[i] >>v[i];
}
dp = new int[W+1];
memset(dp,0,sizeof(int)*(W+1));
for (int i=0; i<n; i++)
{
for (int j=W; j>=w[i]; j--)
{
dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout << dp[W] << endl;
}
JAVA版本解法：
package 记忆化搜索;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int W=sc.nextInt();
int []w=new int[n];
int []v=new int[n];
for (int i = 0; i < v.length; i++) {
w[i]=sc.nextInt();
v[i]=sc.nextInt();
}
int dp[]=new int[W+1];
for (int i=0; i<n; i++)
{
for (int j=W; j>=w[i]; j--)
{
dp[j] = Math.max(dp[j],dp[j-w[i]]+v[i]);
}
}
System.out.println(dp[W]);
}
}
完全背包问题
c++版本解法：
#include <iostream>
#include <cstring>
using namespace std;
int n,W;
int * w;
int * v;
int *dp;
int max(int x, int y)
{
if (x>y) return x;
return y;
}
int main()
{
cin >> n >> W;
w = new int[n];
v = new int[n];
for (int i=0; i<n; i++)
{
cin >> w[i] >>v[i];
}
dp = new int[W+1];
memset(dp,0,sizeof(int)*(W+1));
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] << endl;
}
Java版本解法：
package 记忆化搜索;
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int W=sc.nextInt();
int []w=new int[n];
int []v=new int[n];
for (int i = 0; i < v.length; i++) {
w[i]=sc.nextInt();
v[i]=sc.nextInt();
}
int dp[]=new int[W+1];
for (int i=0; i<n; i++)
{
for (int j=w[i]; j<=W; j++)
{
dp[j] = Math.max(dp[j],dp[j-w[i]]+v[i]);
}
}
System.out.println(dp[W]);
}
}
两者只有关于j的循环方向不同。
除了上面的情况外，还有可能通过将两个数组滚动使用来实现重复利用，例如之前的
dp[i+1][j] = max(dp[i][j], dp[i+1][j-w[i]]+v[i])
这一递推式中，dp[i+1]计算时只需要dp[i]和dp[i+1]，所以可以结合奇偶性写成：
C++版本：
#include <iostream>
#include <cstring>
using namespace std;
int n,W;
int * w;
int * v;
int *dp[2];
int max(int x, int y)
{
if (x>y) return x;
return y;
}
int main()
{
cin >> n >> W;
w = new int[n];
v = new int[n];
for (int i=0; i<n; i++)
{
cin >> w[i] >>v[i];
}
dp[0] = new int[W+1];
dp[1] = new int[W+1];
memset(dp[0],0,sizeof(int)*(W+1));
memset(dp[1],0,sizeof(int)*(W+1));
for (int i=0; i<n; i++)
{
for (int j=0; j<=W; j++)
{
if (j<w[i]) dp[(i+1) & 1][j] = dp[i & 1][j];
else dp[(i+1) & 1][j] = max(dp[i & 1][j],dp[i & 1][j-w[i]]+v[i]);
}
}
cout << dp[n & 1][W] << endl;
}
01背包问题之2
- 问题描述：有n个重量和价值分别为wi、vi的物品，从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。
input：
4
5
2 3
1 2
3 4
2 2
output：
7（选择0、1、3号物品）
这一问题与最初的01背包问题相比，只是修改了限制条件的大小。此前求解此问题的方法的复杂度是O(nW)，对于这一问题的规模来讲就不够用了。在这个问题中，相比较重量而言，价值的范围比较小，所以可以试着改变DP的对象。之前的方法中，我们用DP针对不同的重量限制计算最大的价值，最大值最多为n*最大物品的价值。在这里，我们不妨尝试着用DP针对不同的价值计算最小的重量：
dp[i+1][j] := 从前i+1个物品(编号从0到i)中挑选出价值总和为j时总重量的最小值(不存在时就是一个充分大的数值INF)
由于前0个物品中什么都挑选不了，所以初始值为
dp[0][0] = 0
dp[0][j] = INF
此外，从前i个物品中挑选出价值总和为j时，一定有
①前i-1个物品中挑选价值总和为j的部分
②前i-1个物品中挑选价值总和为j-v[i]的部分，然后再选中第i个物品
这两种方法之一，所以就得到递推式：
dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]]+w[i])
最终的答案就对应于令dp[n][j]≤W的最大的j，这样求解的时间复杂度为O(n∑vi)，对此题限制条件下的输入就可以在时间限制内解出了。当然如果价值变大了的话，这里的算法也变得不可行了，我们需要依据问题的规模来改变算法
c++版本解法：
#include <iostream>
#include <cstring>
using namespace std;
const int INF = 0x3FFFFFF;
int n,W;
int * w;
int * v;
int **dp;
int min(int x, int y)
{
if (x>y) return y;
return x;
}
int main()
{
cin >> n >> W;
w = new int[n];
v = new int[n];
int maxv=0;
for (int i=0; i<n; i++)
{
cin >> w[i] >>v[i];
if (v[i]>maxv) maxv=v[i];
}
dp= new int*[n+1];
for (int i=0; i<=n; i++)
{
dp[i] = new int[n*maxv+1];
for (int j=0; j<=n*maxv; j++) dp[i][j]=INF;
}
dp[0][0] = 0;
for (int i=0; i<n; i++)
{
for (int j=0; j<=n*maxv; j++)
{
if (j<v[i]) dp[i+1][j] = dp[i][j];
else dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]]+w[i]);
}
}
for (int i=n*maxv; i>=0; i--)
if (dp[n][i] <= W)
{
cout << i << endl;
break;
}
}
java解法：
package 记忆化搜索;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int INF=1000;
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int W=sc.nextInt();
int []w=new int[n];
int []v=new int[n];
int maxVal=0;
for (int i = 0; i < v.length; i++) {
w[i]=sc.nextInt();
v[i]=sc.nextInt();
if(maxVal<v[i])
maxVal=v[i];
}
int dp[][]=new int[n+1][n*maxVal+1];
for (int i=0; i<=n; i++)
{
for (int j=0; j<=n*maxVal; j++) dp[i][j]=INF;
}
dp[0][0] = 0;
for (int i=0; i<n; i++)
{
for (int j=0; j<=n*maxVal; j++)
{
if (j<v[i]) dp[i+1][j] = dp[i][j];
else dp[i+1][j] = Math.min(dp[i][j],dp[i][j-v[i]]+w[i]);
}
}
for (int i=n*maxVal; i>=0; i--)
if (dp[n][i] <= W)
{
System.out.println(i);
break;
}
}
}