C/C++之01背包问题

问题描述
　　给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.
输入格式
　　输入的第一行包含两个整数n, m，分别表示物品的个数和背包能装重量。
　　以后N行每行两个数Wi和Vi,表示物品的重量和价值
输出格式
　　输出1行，包含一个整数，表示最大价值。
样例输入
3 5
2 3
3 5
4 7
样例输出
8
数据规模和约定
　　1<=N<=200,M<=5000.
第一种解法，先对背包通过重量排序，当重量不能放入的时候退出，主要方法是dfs+剪枝，但是超时了，可能是数据规模太大，效率不高导致超时

#include<iostream>
#include<algorithm>
using namespace std;
struct node{
	int weight;
	int value;
}arr[200];
int n,w;
int cmp(node n1,node n2)
{
	return n1.weight<n2.weight;
}
int _max=0;
void dfs(int weight,int index)
{
	if(index==n||weight<arr[index].weight)
	{
		if(value>_max)
			_max=value;
		return;
	}
	dfs(weight,value,index+1);
	dfs(weight-arr[index].weight,value+arr[index].value,index+1);
}
int main()
{
	cin>>n>>w;
	sort(arr,arr+n,cmp);
	for(int i=0;i<n;i++)
		cin>>arr[i].weight>>arr[i].value;
	dfs(w,0,0);
	cout<<_max;
}

第二种解法dfs，其实和第一种解法感觉差不多，但是通过结果来看，好像比第一种效果更好，不过还是难逃超时

#include<iostream>
using namespace std;
int w[1000];
int v[1000];
int n;
int W;
int dfs(int i,int ww)
{
	int ans;
	if(ww<=0)
		return 0;
	if(i==n)
		return 0;
	int v2=dfs(i+1,ww);
	if(ww>=w[i])
	{
		int v1=v[i]+dfs(i+1,ww-w[i]);
		ans= max(v1,v2);
	}
	else
		ans= v2;
	return ans;
}
int main()
{
	cin>>n>>W;
	for(int i=0;i<n;i++)
	{
		cin>>w[i]>>v[i];
	}
	int ww=W;
	cout<<dfs(0,ww);	
}

第三种解法，是第二种的剪枝，采用记忆的方法实现剪枝

#include<iostream>
using namespace std;
int w[1000];
int v[1000];
int n;
int W;
int dp[1000][1000];
int dfs(int i,int ww)
{
	int ans;
	if(ww<=0)
		return 0;
	if(i==n)
		return 0;
	if(dp[i][ww]>0)
		return dp[i][ww];
	int v2=dfs(i+1,ww);
	if(ww>=w[i])
	{
		int v1=v[i]+dfs(i+1,ww-w[i]);
		ans= max(v1,v2);
	}
	else
		ans= v2;
	dp[i][ww]=ans;
	return ans;
}
int main()
{
	cin>>n>>W;
	for(int i=0;i<n;i++)
	{
		cin>>w[i]>>v[i];
	}
	int ww=W;
	cout<<dfs(0,ww);	
}

第四种解法，通过迭代求解，主要通过二维数组记录当前节点的最大价值，然后一步步迭代，最终求得结果

#include<iostream>
using namespace std;
int n,w;
int weight[5010];
int value[300];
int dp[300][5010];
int main()
{
	cin>>n>>w;
	for(int i=1;i<=n;i++)
		cin>>weight[i]>>value[i];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=w;j++)
			if(j>=weight[i])
			{
				dp[i][j]=max(dp[i-1][j],value[i]+dp[i-1][j-weight[i]]);
			}
			else
				dp[i][j]=dp[i-1][j];
	cout<<dp[n][w];
	return 0;
}

完全背包

可重复

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
 
int n,m;
int w[5010],v[5010];
int dp[5010][5010];
 
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d",&w[i],&v[i]);
        }
        for(int i=1; i<=n; i++)//数量；
        {
            for(int j=0; j<=m; j++)//背包能放的重量；
            {
                if(j<w[i])//放不下；
                    dp[i][j]=dp[i-1][j];
                else//可以放下，就有放和不放两种选择；
                    dp[i][j]=max(dp[i-1][j],v[i]+dp[i][j-w[i]]);
            }
        }
        printf("%d\n",dp[n][m]);
    }
    return 0;
}