#include <cmath>
#include <cstring>
#include <string.h>
#include <queue>
#include <stack>
#include <map>
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n,m;
int w[N],v[N],dp[205];
int main(){
	cin >> m >> n;
	for(int i=1; i<=n; i++)
	    cin >> w[i] >> v[i];
	for(int i= 1; i<=n; i++){
		for(int j=m; j>=w[i]; j--){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout << dp[m]; 
	return 0;
}
//01背包0一维数组优解，制作不易，点个赞再走吧

#include <bits/stdc++.h>
using namespace std;
int m,n;
int v[200],w[200],dp[200];
int main(){
	cin >> m >> n;
	for(int i = 1;i <= n;i++){
		cin >> v[i] >> w[i];
	}
	for(int i = 1;i <= n;i++){
		for(int j = m;j >= 1;j--){
			if(j - v[i] >= 0){
				dp[j] = max(dp[j - v[i]] + w[i],dp[j]);
			}
		}
	}
	cout << dp[m];
	return 0;
}

时间空间复杂度最小一维数组加注释谁要

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

int main() {
    int m, n; // 背包容量和物品数量
    cin >> m >> n;

    int W[n]; // 物品重量
    int C[n]; // 物品价值

    // 输入物品的重量和价值
    for (int i = 0; i < n; i++) {
        cin >> W[i] >> C[i];
    }

    // dp[j] 表示背包容量为 j 时的最大价值
    int dp[m + 1] = {0}; // 初始化为0，表示容量为0时价值为0

    // 动态规划填表
    for (int i = 0; i < n; i++) { // 遍历每个物品
        for (int j = m; j >= W[i]; j--) { // 倒序遍历背包容量
            dp[j] = max(dp[j], dp[j - W[i]] + C[i]); // 状态转移方程
        }
    }

    // 输出最大价值
    cout << dp[m] << endl;

    return 0;
}

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=310;
const int INF=0x3f3f3f3f;
int dp[N][N],n,m,w[N],c[N]; 
int main()
{
	IOS;
	cin>>m>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>w[i]>>c[i];
	}
	for(int i=1;i<=n;++i)
	{
		for(int v=m;v>0;--v)
		{
			if(v>=w[i])
			    dp[i][v]=max(dp[i-1][v],(dp[i-1][v-w[i]]+c[i]));
			else
			    dp[i][v]=dp[i-1][v];
		}
	}
	cout<<dp[n][m];
    return 0;
}

P1725 0/1背包问题

本人以坑人乐于助人为主

本代码是有很多bug没有注释的

现在我要删掉分享我的代码

这是TeMeGe链接http://luogu.com

这是洛谷链接http://temege.com

现在打出我的假真代码

元神，启动

搞错了

#include
using namespace std;
int W[1010],V[1010];
int dp[1010][1010];
int m,n; 
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)cin>>W[i]>>V[i]; 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(j>=W[i]){
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-W[i]]+V[i]);
			}
			else{
				dp[i][j]=dp[i-1][j];
			}
		}
	} 
	cout<<dp[n][m];
}

单击此链接进入洛谷

P1725 0/1背包问题

背包DP模板题，这个屑蒟蒻并没有压缩状态

注释在CODE挺详细的了

CODE

#include<bits/stdc++.h>
using namespace std;
int W[1010],V[1010];
int dp[1010][1010];//dp[前x件物品][已用重量]=对应最大价值 
int m,n; 
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)cin>>W[i]>>V[i]; 
	for(int i=1;i<=n;i++){//枚举第i件物品 
		for(int j=1;j<=m;j++){//插入第i件物品后重量 
			if(j>=W[i]){//插入后重量肯定得比该物件要重吧…… 
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-W[i]]+V[i]);
				//dp[i-1][j] 即为 不选该物件,不选且重量达到j的最优价值 
				//dp[i-1][j-W[i]]+V[i] 即为 选择该物件,那么,可以得出,在没有选择该物件时，重量为j-W[i] 
				//故在该状态+V[i](对应物品的价格) 
			}
			else{
				dp[i][j]=dp[i-1][j];//见上 
			}
		}
	} 
	cout<<dp[n][m];//输出最优结果 
}

#include using namespace std; int c[10001],w[10001],dp[10001]; int main(){ int m,n; cin>>m>>n; for(int i=1;i<=n;i++){ cin>>w[i]>>c[i]; } for(int i=1;i<=n;i++) for(int j=m;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+c[i]); cout<<dp[m]; }

P1725 0/1背包问题

本人的第n篇题解

这题很简单,用dfs就搞定了！

代码：

#include<iostream>
using namespace std;
int m,n,sumw,sumc,maxnc;//sumw:用来记录重量的总和,sumc:用来记录价值的总和,maxnc:用来记录最大的总和 
bool b[1000000]={0};
struct s{
	int w,c;//w表示重量,c表示价值 
} a[1000000]={0};
void dfs(int x){
	for(int i=x;i<=n;i++){
		if(sumw+a[i].w<=m&&b[i]==0){//判断sumw+这个魔法石的重量会不会超出背包重量，还要判断有没有算过 
			sumw+=a[i].w;//加上重量 
			sumc+=a[i].c;//加上价值 
			b[i]=1;//算过了 
			dfs(i);
			b[i]=0;//还原 
			sumw-=a[i].w;
			sumc-=a[i].c;
		} 
	}
	maxnc=max(sumc,maxnc);//比较最大的 
	return;
}
int main(){
	cin>>m>>n; 
	for(int i=1;i<=n;i++) cin>>a[i].w>>a[i].c;//输入数字 
	dfs(1);
	cout<<maxnc;//输出 
	return 0;
}

制作不易，点个赞再走吧。