本题和A1267. 【例9.11】01背包问题的题意和思路差不多，只是物品变成可以无限拿了（从前往后数也不怕）

详见题解 - 【例9.11】01背包问题

代码

#include <bits/stdc++.h>
using namespace std;
int a[205],w[35],v[35];
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 = w[j];i <= m;i++){// 从前往后数
			a[i] = max(a[i - w[j]] + v[j],a[i]);
		}
	}
	printf("max=%d",a[m]);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int a[1000000];
int a1[100000];
int b1[100000];
int main(){
	int m,n; 
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>a1[i]>>b1[i];
	}
	for(int i=1;i<=m;i++){
	    for(int j=1;j<=n;j++){
	    	if(i>=a1[j]){
	    		a[i]=max(a[i],a[i-a1[j]]+b1[j]);
			}
		}
	}
	cout<<"max="<<a[m];
}

题意

01改版

代码

#include<iostream>
using namespace std;
int m,n;
int wi[114514];
int ci[114514];
int a[114514];
int main()
{
	cin>>m>>n;//输入
	for(int i=0;i<n;i++)
	{
		cin>>wi[i]>>ci[i];//输入
	}
	for(int i=0;i<n;i++)//注意范围
	{
		for(int j=wi[i];j<=m;j++)
		{
			a[j]=max(a[j],a[j-wi[i]]+ci[i]);//取最大价值的物品
		}
	}
	cout<<"max="<<a[m];//输出
	return 0;//完结散花
}

送一个记搜版本的

#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)//重量,物品 
{
	if(x<=0 || i<=0) return 0;
	if(f[x][i]) return f[x][i];
	int ma=dfs(x,i-1);
	for(int k=1;x>=w[i]*k;k++)
		ma=max(ma,dfs(x-w[i]*k,i-1)+c[i]*k);
	return f[x][i]=ma;
}
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)
		cin>>w[i]>>c[i];
	cout<<"max="<<dfs(m,n);
	return 0; 
}

题意

不日，经典模板题你让我写题意？？？

死路

把一个无限物品$a_i$当成$m/w_i$个有限物品

问题

其实也是经典思路之一，但是不好写。

思路

仿照纸币问题1，用一个数组终结一切！

就是靠以前的推现在的。

状态转移方程

DP特有部分

$f_i$表示背包容量为i时的最大价值

$f_{i-w_x}+c_x$就是放了物品$a_x$时的状态

代码

#include<iostream>
using namespace std;
int f[300];
int main(){
	int m,n;
	cin>>m>>n;
	int w[n],c[n];
	for(int i=0;i<n;i++)
		cin>>w[i]>>c[i];
	f[0]=0;//背包容量为0时最大价值为0
	for(int i=0;i<=m;i++)
		for(int x=0;x<n;x++)
			if(i-w[x]>=0)//守护边界，谨防RE
				f[i]=max(f[i-w[x]]+c[x],f[i]);
	cout<<"max="<<f[m];
}

注意

最后输出要加“max=”

#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,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];
	printf("max=%d",dfs(n,m));
	return 0;
}

来了