动态规划的用法——01背包问题

问题主题：著名的01背包问题

问题描述：

有n个重量和价值分别为wi、vi的物品，现在要从这些物品中选出总重量不超过W的物品，求所有挑选方案中的价值最大值。

限制条件：

1<=N<=100

1<=wi 、vi<=100

1<=wi<=10000

样例：

输入

N=4

W[N] = {2, 1, 3, 2}

V[N] = {3, 2, 4, 2}

输出

W = 5(选择0，1，3号)

【解法一】

解题分析：

用普通的递归方法，对每个物品是否放入背包进行搜索

程序实现:

C++

#include <stdio.h>

include <tchar.h>

include <queue>

include "iostream"

using namespace std;

const int N = 4;
const int W = 5;
int weight[N] = {2, 1, 3, 2};
int value[N] = {3, 2, 4, 2};
int solve(int i, int residue)
{
int result = 0;
if(i >= N)
return result;
if(weight[i] > residue)
result = solve(i+1, residue);
else
{
result = max(solve(i+1, residue), solve(i+1, residue-weight[i]) + value[i]);
}

}

int main() {
int result = solve(0, W);
cout << result << endl;
return 0;
}

【解法二】

解题分析：

用记录结果再利用的动态规划的方法，上面用递归的方法有很多重复的计算，效率不高。我们可以记录每一次的计算结果，下次要用时再直接去取，以提高效率

程序实现:

C++

#include <stdio.h>

include <tchar.h>

include <queue>

include "iostream"

using namespace std;

const int N = 4;
const int W = 5;
int weight[N] = {2, 1, 3, 2};
int value[N] = {3, 2, 4, 2};
int record[N][W];
void init()
{

for(int i = 0; i &lt; N; i ++)
{
	for(int j = 0; j &lt; W; j ++) 
	{
		record[i][j] = -1;
	}
}

}

int solve(int i, int residue)
{

if(-1 != record[i][residue])
	return record[i][residue];
int result = 0;
if(i &gt;= N)
	return result;
if(weight[i] &gt; residue)
{
	record[i + 1][residue] = solve(i+1, residue);
	
}
else 
{
	result = max(solve(i+1, residue), solve(i+1, residue-weight[i]) + value[i]);
}
return record[i + 1][residue] = result;

}

int main() {

init();
int result = solve(0, W);
cout &lt;&lt; result &lt;&lt; endl;
return 0;

}

Java

package greed;

/**

User: luoweifu
Date: 14-1-21

Time: 下午5:13
*/
public class Knapsack {
private int maxWeight;
private int[][] record;
private Stuff[] stuffs;

public Knapsack(Stuff[] stuffs, int maxWeight) {

this.stuffs = stuffs;
this.maxWeight = maxWeight;
int n = stuffs.length + 1;
int m = maxWeight+1;
record = new int[n][m];
for(int i = 0; i &lt; n; i ++) {
	for(int j = 0; j &lt; m; j ++) {
		record[i][j] = -1;
	}
}

}
public int solve(int i, int residue) {

if(record[i][residue] &gt; 0) {
	return record[i][residue];
}
int result;
if(i &gt;= stuffs.length) {
	return 0;
}
if(stuffs[i].getWeight() &gt; residue) {
	result = solve(i + 1, residue);
} else {
	result = Math.max(solve(i + 1, residue),
		 solve(i + 1, residue - stuffs[i].getWeight()) + stuffs[i].getValue());
}
record[i][residue] = result;
return result;

}

public static void main(String args[]) {

Stuff stuffs[] = {
	new Stuff(2, 3),
	new Stuff(1, 2),
	new Stuff(3, 4),
	new Stuff(2, 2)
};
Knapsack knapsack = new Knapsack(stuffs, 5);
int result = knapsack.solve(0, 5);
System.out.println(result);

}
}

class Stuff{

private int weight;
private int value;

public Stuff(int weight, int value) {
	this.weight = weight;
	this.value = value;
}

int getWeight() {
	return weight;
}

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

int getValue() {
	return value;
}

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

} <pre/>

算法复杂度：

时间复杂度O(NW)