面试OR笔试41——01背包

1.1 题目描述

有n 个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

解法解析见博客动态规划解决01背包问题

这里给出三种解法。

2.1 代码

#include 
#include 
#include 
#include 
#include 
using namespace std;

// 一维动态规划, 无方案输出
int package(const vector &w, const vector &v, int c) {
	int wn(w.size()), vn(v.size());
	wn  dt(c + 1, 0);
	for (int k1(0);k1  &w, const vector &v, int wn, int k, int c, int val, vector &status) {
	if (wn == k) return val;
	status[k] = false;
	if (c  &w, const vector &v, int c, vector &out) {
	int wn(w.size()), vn(v.size());
	wn  status(wn, false);
	int val(package1(w, v, wn, 0, c, 0, status));
	out.clear();
	for (int k1(0);k1  &w, const vector &v, int c, vector &out) {
	int wn(w.size()), vn(v.size());
	wn  > dt(wn+1, vector(c + 1, 0));
	for (int k1(0);k1  w = { 2,3,4,5 }, v = { 3,4,5,6 };
	vector o;
	int c = 8;
	cout <<"weight  : ";
	for (auto i : w) cout <