【算法设计与分析】 0-1背包问题（动态规划）

【算法设计与分析】 0-1背包问题（动态规划）

【问题描述】
使用动态规划算法解0-1背包问题，具体来说就是，依据递归式，按照顺序求得子问题，使得选择合适物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

【输入形式】
在屏幕上输入背包容量、物品数量、每件物品价值和重量。

【输出形式】
最优解时所选物品的价值总和及其编号。

【样例输入】

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

【样例输出】

15
1 2 5
1
2

【样例说明】
输入：背包容量10、物品数量5、每件物品价值6, 3, 5, 4, 6和重量2, 2, 6, 5, 4。
输出：最优解时选择物品的价值总和为15，编号为1,2,5。

【题解代码】

C++代码：

#include <iostream>
#include <cstdio>
using namespace std;
int c,n,v[1000],w[1000],x[1000],m[1000][1000];
void Knapsack(int v[],int w[],int c,int n,int m[][1000])
{
	int jmax=min(w[n]-1,c);
	for(int j=0;j<=jmax;j++)
		m[n][j]=0;
	for(int j=w[n];j<=c;j++)
		m[n][j]=v[n];
	for(int i=n-1;i>1;i--)
	{
		jmax=min(w[i]-1,c);
		for(int j=0;j<=jmax;j++)
			m[i][j]=m[i+1][j];
		for(int j=w[i];j<=c;j++)
			m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
	}
	m[1][c]=m[2][c];
	if(c>=w[1])
		m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
}
void Traceback(int m[][1000],int w[],int c,int n,int x[])
{
	for(int i=1;i<n;i++)
	{
		if(m[i][c]==m[i+1][c])
			x[i]=0;
		else
		{
			x[i]=1;
			c-=w[i];
		}
	}
	x[n]=m[n][c]?1:0;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>c>>n;
	for(int i=1;i<=n;i++)
		cin>>v[i];
	for(int i=1;i<=n;i++)
		cin>>w[i];
	Knapsack(v,w,c,n,m);
	Traceback(m,w,c,n,x);
	cout<<m[1][c]<<endl;
	for(int i=1;i<=n;i++)
		if(x[i]==1)
			cout<<i<<" ";
	cout<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54