01背包

题面

试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数，并将此函数用于解 0-1 背包问题。0-1 背包问题描述如下：给定 n 种物品和一个背包。物品 i 的重量是w_i，其价值为v_i，背包的容量为C 。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。

第一行有2个正整数n和Cn是物品数C是背包的容量。接下来的 1 行中有 n 个正整数，表示物品的价值。第3行中
有 n 个正整数，表示物品的重量。 

将计算出的装入背包物品的最大价值和最优装入方案输出。第一行输出为：Optimal value is

输入

5 10
6 3 5 4 6
2 2 6 5 4

输出

Optimal value is
15
1 1 0 0 1

dfs代码（超时）

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<unordered_map>
#include<queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 100;

int n, c,ans;
bool st[N];
bool used[N];
double w[N], v[N];
double a[N], b[N];

struct node {
	double w, v;
	int idx;
}z[N];

void dfs(int u, int ww, int vv)
{
	
	if (ww + w[u] <= ans) return;

	if (u > n) {
		int t = ans;
		ans = max(ans, ww);
		if(ans!=t)memcpy(used, st, n);
		return;
	}

	if (vv + b[u] <= c) {
		st[z[u].idx] = true;
		dfs(u + 1, ww + a[u], vv + b[u]);
	}
	

	st[z[u].idx] = false;
	dfs(u + 1, ww, vv);


}

bool cmp(node a, node b)
{
	return a.w/a.v > b.w/a.v;
}

int main()
{
	cin >> n >> c;

	for (int i = 0; i < n; i++) {
		cin >> z[i].w;
		z[i].idx = i;
	}
	

	for (int i = 0; i < n; i++) cin >> z[i].v;
	
	sort(z, z + n, cmp);

	for (int i = 0; i < n; i++)
	{
		w[i] = a[i] = z[i].w;
		v[i] = b[i] =  z[i].v;
	}

	for (int i = n - 2; i >= 0; i--)
	{
		w[i] += w[i + 1];
		v[i] += v[i + 1];
	}

	cout << "Optimal value is" << endl;

	dfs(0,0,0);

	cout << ans << endl;

	for (int i = 0; i < n; i++)
		cout << used[i] << " ";

	return 0;
}

记忆化搜素(未超时)

#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>

using namespace std;

const int N = 1010;

int n,t,ans;
int v[N], w[N];
int a[N][N];
bool st1[N], st2[N];

void dfs(int u, int money, int weight)
{
	if (weight > t)return;

	if (a[u][weight])
	{
		if (money < a[u][weight])return;
	}

	a[u][weight] = money;

	if (u == n)
	{
		int t = ans;
		ans = max(ans, money);
		if(ans!=t)
		for (int i = 0; i < n; i++)st2[i] = st1[i];
		return;
	}

	st1[u] = 1;
	dfs(u + 1, money + v[u], weight + w[u]);

	st1[u] = 0;
	dfs(u + 1, money, weight);
}

int main()
{
	cin >> n>>t;

	for (int i = 0; i < n; i++)cin >> v[i];
	for (int i = 0; i < n; i++)cin >> w[i];

	dfs(0, 0, 0 );
	cout << "Optimal value is" << endl;
	cout << ans << endl;

	for (int i = 0; i < n; i++)cout << st2[i] << " ";

}

dp代码（没问题）

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<unordered_map>
#include<queue>

using namespace std;

const int N = 1005;
int v[N];   
int w[N];  
int f[N];
bool st[N];
bool path[N][N];

int main()
{
	int n, c;
	cin >> n >> c;
	for (int i = 1; i <= n; i++)
		cin  >> w[i];
	for (int i = 1; i <= n; i++)
		cin >> v[i];

	for (int i = 1; i <= n; i++)
		for (int j = c; j >= v[i]; j--)
		{
			if (f[j] < f[j - v[i]] + w[i])
			{
				f[j] = f[j - v[i]] + w[i];
				path[i][j] = 1;
			}
			else
			{
				f[j] = f[j];
				path[i][j] = 0;
			}

		}

	cout <<"Optimal value is" <<endl<< f[c] << endl;
	int i = n, j = c,tt = n;
	while (i >= 1 && j >= 0)
	{
		if (path[i][j])
		{
			st[tt--] = 1;
			j -= v[i];
		}
		else st[tt--] = 0;
		i--;
	}

	for (int i = 1; i <= n; i++)cout << st[i] << " ";

	return 0;

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>

using namespace std;

typedef long long LL;

const int N = 3505;

LL n,m;
LL f[N];


int main()
{
	cin >> n>>m;

    for (int i = 1; i <= n; i++) {
        LL v, w;
        cin >> v >> w;   
        for (int j = m; j >= v; j--)
            f[j] = max(f[j], f[j - v] + w);
    }

	cout << f[m];

	return 0;
}