分别使用swift和java—利用动态规划法求解01背包问题
程序员文章站
2022-06-08 13:55:13
...
问题描述：
给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 Wi，其价值为 Vi 。
问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
求解思路：
有2种解题思路：动态规划法和穷举法。
1.穷举法此方法需配合剪技算法，不然时间复杂度为2的n次方，此处略。
2.动态规划法
csdn中关于此方法的思路讲的非常多，此处略，例如：
https://blog.csdn.net/xp731574722/article/details/70766804
https://blog.csdn.net/baidu_28312631/article/details/47418773
下面是利用动态规划法分别用swift和java写的代码，分别在xcode8.0和eclipase上调试成功，作为练手之用，高手跳过。
完整代码下载链接：
https://download.csdn.net/download/qq_42439742/10714746
SWIFT
XCODE程序运行结果：
01背包问题：
背包最大容量为：8
物品清单如下：
id：1, W=2,V=3
id：2, W=3,V=4
id：3, W=4,V=5
id：4, W=5,V=6
最大的价值为：10
被选中的物品为：
id：2, W=3,V=4
id：4, W=5,V=6
Program ended with exit code: 0
以下是swift完整代码：
//
// main.swift
// 01背包问题
//
// Created by terry on 2018/10/7.
// Copyright © 2018年 terry. All rights reserved.
//此处为动态规划法
import Foundation
//物品的数据结构
struct WuPin {
var id //ID
var W //物品体积（或者重量）
var V //物品价值
var isUser = 0 //是否被使用，0：未使用。1：已使用
init(id:Int,W:Int,V:Int) {
self.id = id
self.W = W
self.V = V
}
}
/// 动态规划法求解01背包问题
class BeiBao{
private var number:Int //物品数量
private var C:Int //背包最大体积(或者是最大重量)
private var wuPins:[WuPin] = [] //物品数组(包含编号，体积，价值、是否使用)
private var V:[[Int]] = [] // 所选物品的最大价值，V[I][J]的二维数组
/// 构造函数,初始化
///
/// - Parameters:
/// - number: 物品数量
/// - C: 背包最大体积
init(number:Int,C:Int) {
self.C = C
self.number = number
self.V = getArray2() //生成V[i][j]的二维数组
print("01背包问题：\n")
print("背包最大容量为：\(C) \n")
setWuPins() . //按默认值生成物品列表
print("物品清单如下：")
echoWuPing() . //显示物品清单
}
/// 生成物品数组
private func setWuPins() {
for i in 0...number {
//增加一个编号为0的虚拟物品，其W=0,V=0，作为数组的边界存在
//假定,当i=1时，W=2，V=3，以此类推
if i==0 {
wuPins.append(WuPin(id: 0, W: 0, V: 0))
}
else{
wuPins.append(WuPin(id: i, W: i+1, V: i+2))
}
}
}
/// 显示所有物品清单
func echoWuPing() {
for wupin in wuPins {
if wupin.id != 0 { //排除id=0的虚拟物品
print("id：\(wupin.id), W=\(wupin.W),V=\(wupin.V) \n")
}
}
}
/// 显示未选中或已被选中的物品清单
///
/// - Parameter isUser: 0:未选中。1：被选中
func echoWuPing(isUser:Int) {
if isUser==0 {
print("未选中的物品为：")
}
else{
print("被选中的物品为：")
}
//wuPins[0]为虚拟物品，排除
for i in 1..<wuPins.count {
if wuPins[i].isUser == isUser {
print("id：\(wuPins[i].id), W=\(wuPins[i].W),V=\(wuPins[i].V) \n")
}
}
}
/// 返回全部填充为0的二维数组：V[number][C]
///
/// - Returns: 全部填充为0的二维数组
private func getArray2() -> [[Int]] {
var result:[[Int]] = []
//生成二维数组中的行
var row:[Int] = []
for _ in 0...C{
row.append(0)
}
//生成二维数组中的列
for _ in 0...number{
result.append(row)
}
return result
}
/// 求解如何放物体得到最大价值问题，用填表方式进行
///
/// - Returns: 返回最大价值
func findMax_dongTaiGuiHua() -> Int {
//i=0,j=0为边界，在二维数组填充时已全部填充为0，作为数组边界。此处从i=1，j=1开始
//i为物品编号，j为剩余最大空间容量，从0-j依次填表
for i in 1...number{
for j in 1...C{
if j < wuPins[i].W{ //如果剩余空间容量<物品的容量，则放不进
V[i][j] = V[i-1][j] //因为需要调动[i-1]，所以要从[1]开始，并且[0]一定要有值，即需要数组边界
}
else{
if V[i-1][j] > V[i-1][j-wuPins[i].W]+wuPins[i].V{ //不装价值更大
V[i][j] = V[i-1][j]
}
else{ //装价值更大
V[i][j] = V[i-1][j-wuPins[i].W]+wuPins[i].V
}
}
}
}
return V[number][C] . //表格中最后一位即为最大价值
}
/// 查找哪些物品被选中,带参数i,j是为了实现递归
///
/// - Parameters:
/// - i: 物品数，从最大值开始
/// - j: 剩余空间容量，从最大值开始
func findWhat(i:Int,j:Int) {
if i>0 {
if V[i][j] == V[i-1][j]{ //说明没有选入
wuPins[i].isUser = 0
findWhat(i: i-1, j: j)
}
else{
if j-wuPins[i].W >= 0 && V[i][j] == V[i-1][j-wuPins[i].W] + wuPins[i].V{
wuPins[i].isUser = 1
findWhat(i: i-1, j: j-wuPins[i].W)
}
}
}
}
}
let number = 4 //常量：物品个数
let C = 8 //常量：背包最大空间容量
let beibao = BeiBao(number: number, C: C)
print("最大的价值为：\(beibao.findMax_dongTaiGuiHua())")
beibao.findWhat(i: number, j: C)
beibao.echoWuPing(isUser: 1)
JAVA
下面是JAVA代码，在eclipse上调试成功
程序运行结果：
所有物品清单为：
ID:1,W=2,V=3
ID:2,W=3,V=4
ID:3,W=4,V=5
ID:4,W=5,V=6
二维数组填表如下：
0 3 3 3 3 3 3 3
0 3 4 4 7 7 7 7
0 3 4 5 7 8 9 9
0 3 4 5 7 8 9 10
最大价值为：10
已使用物品清单为：
ID:2,W=3,V=4
ID:4,W=5,V=6
//动态规划法求01背包问题
//n个物品放到总容量为C的背包中，如果放会使价值最大化。(第n个物品的体积为Wn，价值为Cn)
package dongtaiguihua;
class Wupin{
int id; //物品ID
int w; //体积
int v; //价值
int isUser=0; //是否被使用,默认为0，其中1：被使用
public Wupin(int id,int w,int v) {
this.id=id;
this.w=w;
this.v=v;
}
}
class MaxV{
int n; //物品数量
int C; //背包最大价值
Wupin[] wupins; //物品列表
int[][] V ;//V[i][j]的二维数组
public MaxV(int n,int C) {
this.n=n;
this.C=C;
V = new int[n+1][C+1];
//初始化边界
for (int i = 0; i <= C; i++) {
V[0][i]=0;
}
for(int i=0;i<=n;i++) {
V[i][0]=0;
}
//生成物品清单
//假设物品i的w=i+1,v=v+2
wupins = new Wupin[n+1];
for (int i = 0; i <= n; i++) {
if (i==0) {
wupins[i]=new Wupin(0, 0, 0); //虚拟物品，对应数组边界
}
else {
wupins[i]=new Wupin(i, i+1, i+2);
}
}
echoWupins(2); //显示所有物品
}
//显示已使用或者未使用的物品,0：未使用；1：已使用。其它数字：全部
public void echoWupins(int isUse) {
//显示未使用物品
if (isUse==0) {
System.out.println("末使用物品清单为：");
for (int i = 1; i < wupins.length; i++) {
if (wupins[i].isUser==0) {
System.out.println("ID:"+wupins[i].id+",W="+wupins[i].w+",V="+wupins[i].v);
}
}
}
//显示已使用物品
else if (isUse==1) {
System.out.println("已使用物品清单为：");
for (int i = 1; i < wupins.length; i++) {
if (wupins[i].isUser==1) {
System.out.println("ID:"+wupins[i].id+",W="+wupins[i].w+",V="+wupins[i].v);
}
}
}
//显示全部物品
else {
System.out.println("所有物品清单为：");
for (int i = 1; i < wupins.length; i++) {
System.out.println("ID:"+wupins[i].id+",W="+wupins[i].w+",V="+wupins[i].v);
}
}
}
//填表法计算最大价值
public void getMaxV() {
System.out.println("\n二维数组填表如下：");
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= C; j++) {
if (j<wupins[i].w) {
V[i][j]=V[i-1][j];
}
else {
V[i][j]=Math.max( V[i-1][j] , V[i-1][j-wupins[i].w]+wupins[i].v );
}
System.out.print(V[i][j]+" ");
}
System.out.print("\n");
}
System.out.println("最大价值为：" + V[n][C]);
}
//查找哪些物品被选中，从最右下角 从后向前递归
void findMaxWupin(int i,int j) {
if (i>0) {
if (V[i][j] == V[i-1][j]) {
findMaxWupin(i-1, j);
}
else {
if (j>=wupins[i].w && V[i][j]==V[i-1][j-wupins[i].w]+wupins[i].v) {
wupins[i].isUser = 1; //设置已使用标志
findMaxWupin(i-1, j-wupins[i].w);
}
}
}
｝
}
public class Beibao {
public static void main(String[] args) {
int n=4;
int C=8;
MaxV maxV=new MaxV(n, C);
maxV.getMaxV();
maxV.findMaxWupin(n, C);
maxV.echoWupins(1);
}
}