第六章 背包问题——01背包

#include <iostream>
#include <algorithm>
using namespace std;
#define N 3//物品个数
#define V 10//背包容量

int dp[N+1][V+1];
int C[N+1]={0,10,5,5};	//Ci表示第i件物品的费用	 （i从1开始）
int W[N+1]={0,2,2,1};	//W[i]表示第i件物品的价值

int ZeroOnePack(){
	for(int i=1;i<=N;i++){
		for(int v=C[i];v<=V;v++)
		dp[i][v]=max(dp[i-1][v],dp[i-1][v-C[i]]+W[i]);
	}
	return dp[N][V];
}
int main()
{
	memset(dp,0,sizeof(dp));//先对dp初始化
	cout<<ZeroOnePack();
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
#define N 3//物品个数
#define V 10//背包容量

int C[N+1]={0,10,5,5};	//Ci表示第i件物品的费用	 （i从1开始）
int W[N+1]={0,2,2,1};	//W[i]表示第i件物品的价值
int dp[V+1];

int ZeroOnePack(){
	for(int i=1;i<=N;i++){
		for(int v=V;v>=C[i];v--)
		dp[v]=max(dp[v],dp[v-C[i]]+W[i]);
	}
	return dp[V];
}
int main()
{
	memset(dp,0,sizeof(dp));//先对dp初始化
	cout<<ZeroOnePack();
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

#define N 3//物品个数
#define V 10//背包容量

int C[N+1]={0,10,5,5};	//Ci表示第i件物品的费用	 （i从1开始）
int W[N+1]={0,2,2,1};	//W[i]表示第i件物品的价值

int ZeroOnePack(int i,int v){
	if(i<=0||v<=0)return 0;
	
	//不选第i件物品
	int a=ZeroOnePack(i-1,v);
	//必须得保证剩下的容量v能够有C[i]的容量，才能选择第i件物品
	int b=v>=C[i]?ZeroOnePack(i-1,v-C[i])+W[i]:0;
	return max(a,b);
}
int main()
{
	cout<<ZeroOnePack(N,V);
    return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define INF -0x7ffffff
#define N 3//物品个数
#define V 10//背包容量

int C[N+1]={0,10,4,5};	//Ci表示第i件物品的费用	 （i从1开始）
int W[N+1]={0,2,2,1};	//W[i]表示第i件物品的价值
vector<int> dp;

int ZeroOnePack(){
	for(int i=1;i<=N;i++){
		for(int v=V;v>=C[i];v--)
		dp[v]=max(dp[v],dp[v-C[i]]+W[i]);
	}
	return dp[V];
}
int main()
{
	dp.assign(V+1,INF);//dp初始化为负无穷
	dp[0]=0;
	cout<<ZeroOnePack();
    return 0;
}