0-1背包问题（回溯法）

0-1背包问题
有n个重量分别为{w1，w2，…，wn}的物品，它们的价值分别为{v1，v2，…，vn}，给定一个容量为W的背包。设计从这些物品中选取一部分物品放入该背包的方案，每个物品要么选中要么不选中，要求选中的物品不仅能够放到背包中，而且重量和为W具有最大的价值。

回溯法是深度优先遍历，时间复杂度是0(2^n) ：

Java代码实现如下:

//货物实体类
public class Knapsack implements Comparable<Knapsack> {
    /** 物品重量 */
    private int weight;
    /** 物品价值 */
    private int value;
    /** 单位重量价值 */
    private int unitValue;

    public Knapsack(int weight, int value) {
        this.weight = weight;
        this.value = value;
        this.unitValue = (weight == 0) ? 0 : value / weight;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public int getUnitValue() {
        return unitValue;
    }

    @Override
    public int compareTo(Knapsack snapsack) {
        int value = snapsack.unitValue;
        if (unitValue > value)
            return 1;
        if (unitValue < value)
            return -1;
        return 0;
    }

}

//处理回溯类
public class SolveProblem {
    // 待选择的物品
    private Knapsack[] bags;
    // 背包的总承重
    private int totalWeight;
    // 背包的当前承重
    private int currWeight;
    // 待选择物品数量
    private int n;
    // 放入物品后背包的最优价值
    private int bestValue;
    // 放入物品和背包的当前价值
    private int currValue;

    public SolveProblem (Knapsack[] bags, int totalWeight) {
        this.bags = bags;
        this.totalWeight = totalWeight;
        this.n = bags.length;

        // 物品依据单位重量价值从大到小进行排序
        Arrays.sort(bags, Collections.reverseOrder());
    }

    public int solve(int i) {

        // 当没有物品可以放入背包时，当前价值为最优价值
        if (i  == n) {
            if(currValue > bestValue) {
                 bestValue = currValue;
                 return;
            }
        }

        // 首要条件：放入当前物品，判断物品放入背包后是否小于背包的总承重
        if (currWeight + bags[i].getWeight() <= totalWeight) {
            // 将物品放入背包中的状态
            currWeight += bags[i].getWeight();
            currValue += bags[i].getValue();

            // 选择下一个物品进行判断
            solve(i + 1);

            // 将物品从背包中取出的状态
            currWeight -= bags[i].getWeight();
            currValue -= bags[i].getValue();
        }

        // 次要条件：不放入当前物品，放入下一个物品可能会产生更优的价值，则对下一个物品进行判断
        // 当前价值+剩余价值<=最优价值，不需考虑右子树情况，由于最优价值的结果是由小往上逐层返回
        if (currValue + getSurplusValue(i + 1) > bestValue) {
            // 选择下一个物品进行判断
            solve(i + 1);
        }
        return bestValue;
    }

    // 获得物品的剩余总价值 （限界函数进行剪枝）
    public int getSurplusValue(int i) {
        int surplusValue = 0;
        for (int j = i; j < n; j++)
            surplusValue += bags[i].getValue();
            return surplusValue;
    }

}

//开测试
public class Test {
    public static void main(String[] args) {
    Knapsack[] bags = new Knapsack[] { new Knapsack(2, 13),
            new Knapsack(1, 10), new Knapsack(3, 24), new Knapsack(2, 15),
            new Knapsack(4, 28), new Knapsack(5, 33), new Knapsack(3, 20),
            new Knapsack(1, 8) };
    int totalWeight = 12;
    SolveProblem problem = new SolveProblem(bags, totalWeight);
    System.out.println(problem.solve(0));
}
}

完全装满背包变形，c++ 普通递归实现：
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int knap(int W[],int n,int T){
    if(T == 0) return 1;
    if(T < 0 || (n == 0 && T > 0 )) return 0;
    if(knap(W,n-1,T-W[n-1]) == 1){
        printf("第%d个物品，体积为：%d\n",n,W[n-1]);
        return 1;
    }else{
        return knap(W,n-1,T);
    }
} 
int main(void)
{
    int T=10,n=6,W[6]={0,3,6,0,7,9};
    knap(W,n,T);
    return 0;
    }