权 长度438 威

#include<bits/stdc++.h>
using namespace std;
int w[1005],v[1005],bp,n; 
int dp[10005][10005];

int main(){
	cin>>bp>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=n;i++){
		for(int sp=1;sp<=bp;sp++){
			if(w[i]>sp){
				dp[i][sp]=dp[i-1][sp];
			}
			else{
				dp[i][sp]=max(dp[i-1][sp],dp[i-1][sp-w[i]]+v[i]);
			}
		}
	}
	cout<<dp[n][bp];
	return 0;
}/*
for(int i=1;i<=n;i++){
		
	}
*/

记搜好用

#include<iostream>
#define N 35
#define M 205
using namespace std;
int m,n;
int w[N];
int c[N];
int f[M][N];
int dfs(int x,int i)//DP->记搜 四部曲 
{
	//1.判界 
	if(x<=0 || i<=0)
		return 0;
		
	//2.查存 
	if(f[x][i])
		return f[x][i];
	
	//3.放不下 
	if(x<w[i])
		return f[x][i]=dfs(x,i-1);
		
	//4.分类 
	return f[x][i]=max(dfs(x-w[i],i-1)+c[i],dfs(x,i-1));
}
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)
		cin>>w[i]>>c[i];
	cout<<dfs(m,n);
}

送上精简代码

#include<iostream>
using namespace std;
int m,n,w[35],c[35],f[205][35];
int dfs(int x,int i)
{
	if(x<=0 || i<=0) return 0;
	if(f[x][i]) return f[x][i];
	return f[x][i]=max(x>=w[i]?dfs(x-w[i],i-1)+c[i]:0,dfs(x,i-1));
}
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)
		cin>>w[i]>>c[i];
	cout<<dfs(m,n);
	return 0; 
}

#include <iostream> 
using namespace std; 
int c[10001],w[10001],dp[10001];//三个数组，c用来存物品的价值，w用来存物品的重量（占的空间），dp是动规数组 
int main(){ 
	int bag_big_small , things_number; 
	cin >> bag_big_small >> things_number;//输入背包的容量和物品的数量 
	for(int i = 1;i <= things_number;i++){//通过输入的物品数量来进行滚动输入 
		cin >> w[i] >> c[i];//输入物品的重量和价值 
	} 
	for(int i = 1;i <= things_number;i++)//遍历每一个物品的下标 
	for(int j = bag_big_small;j >= w[i];j--)//以背包容量为引，背包容量大于物品的重量就可以继续，注意是j-- 
		dp[j] = max(dp[j] , dp[j - w[i]] + c[i]); //比较dp[j]（不将此物品装入）和dp[j - w[i]] + c[i](将此物品装入)的大小，取大 
	cout << dp[bag_big_small];//输出dp数组中下标为背包容量的位置的数字 
	return 0; 
}

题意

有 $n$ 个物品，一个 $m$ 大小的背包。让背包里的价值最大

物品：有重量（占的空间） $w$ 和价值 $v$

思路

$a_{i,j}$ 的意思是第 $i$ 个重量，前 $j$ 个物品的最大价值

这个物品有两种状态：拿和不拿

拿的话就要将上一个物品丢掉，然后将这个物品装进背包（$a_{i,j} = a_{i - w_j,j - 1} + v_j$）

代码（未优化）

#include <bits/stdc++.h>
using namespace std;
int a[205][35],w[35],v[35];	// a：i 个重量，前 j 个物品时能存的最大价值
int main(int argc, char **argv){
	int n,m;
	cin >> m >> n;
	for (int i = 1;i <= n;i++){
		cin >> w[i] >> v[i];	// 重量和价值
	}
	for (int j = 1;j <= n;j++){	// 遍历物品
		for (int i = 1;i <= m;i++){	// 遍历重量
			if (i < w[j])	a[i][j] = a[i][j - 1];	// 前 w[j] 个重量时，这个物品放不下来
			else	a[i][j] = max(a[i - w[j]][j - 1] + v[j],a[i][j - 1]);	// 左边是拿这个物品，右边是不拿
		}
	}
	cout << a[m][n];
	return 0;
}

思路（新）

提问

能不能优化一下呢？

时间不能优化，因为每一个重量要从上一个物品那里拿过来，不然会影响下一个物品

那就优化空间

做法

二维数组优化到一维数组

当前物品遍历完所有重量后，到下一个物品

下一个物品算出来后直接覆盖

注意：

要从后往前遍历重量，因为从前往后遍历，就会把上一个物品的值覆盖掉，后面的重量就用不了上一个物品的数据了

代码（优化）

#include <bits/stdc++.h>
using namespace std;
int a[205],w[35],v[35];	// a 从二维数组压缩成一维
int main(int argc, char **argv){
	int n,m;
	cin >> m >> n;
	for (int i = 1;i <= n;i++){
		cin >> w[i] >> v[i];	// 重量和价值
	}
	for (int j = 1;j <= n;j++){	// 遍历物品
		for (int i = m;i >= w[j];i--){	// 为确保上一个物品的值不被覆盖，要从后往前数
			a[i] = max(a[i - w[j]] + v[j],a[i]);	// 左边是拿这个物品，右边是不拿这个物品
		}
	}
	cout << a[m];
	return 0;
}

#define ll long long
#include<bits/stdc++.h>
using namespace std;
int m,n;
int w[1005],C[1005];
int vst[1005][1005]={};
//存记忆搜索 
int dfs(int i,int c){
	if(i==0||c==0) return 0;
	//全部枚举完 或  无内存 则 结束 
	if(vst[i][c]) return vst[i][c];
	//如果以前有存记忆就直接返回 
	if(w[i-1]>c) return dfs(i-1,c);
	//容量不够 只能放弃 
	int ifn=dfs(i-1,c);
	//如果不选择 
	int ify=dfs(i-1,c-w[i-1])+C[i-1];
	//如果选择 
	vst[i][c]=max(ifn,ify);
	//存储记忆化答案 
	return vst[i][c];
}
//dfs枚举答案 
int main(){
	cin>>m>>n;
	for(int i=0;i<n;i++) cin>>w[i]>>C[i];
	cout<<dfs(n,m)<<"\n";
	return 0;
}

回来吧我的递归 我最骄傲的信仰👀️

滚动数组，从后往前从而保证需要的数据不被覆盖

#include<bits/stdc++.h>
using namespace std;
struct s{
    int w,c;
};
s arr[210];
int f[210];
int main(){
    int m,n;
    cin>>m>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i].w>>arr[i].c;
    }
    f[0]=0;
    for(int i=0;i<=n;i++){
        for(int j=m-1;j>=arr[i].w-1;j--){
            f[j]=max(f[j-arr[i].w]+arr[i].c,f[j]);
        }
    }
    cout<<f[m-1];
    return 0;
}