动态规划的用法——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号)

#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;
}

#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 < N; i ++)
	{
		for(int j = 0; j < 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 >= N)
		return result;
	if(weight[i] > 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 << result << endl;
	return 0;
}

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 < n; i ++) {
			for(int j = 0; j < m; j ++) {
				record[i][j] = -1;
			}
		}
	}
	public int solve(int i, int residue) {
		if(record[i][residue] > 0) {
			return record[i][residue];
		}
		int result;
		if(i >= stuffs.length) {
			return 0;
		}
		if(stuffs[i].getWeight() > 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;
	}
}