题解bys00000b

可以动态转换此方程为f[i][x]=max(f[i-1][x-w[i]]+c[i],f[i-1][x]) f[n][m]即是最优解

以下为AC代码：

#include <bits/stdc++.h>
using namespace std;

int w[1001],c[1001],f[1001][1001];

int main() {

int m,n;
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
	scanf("%d%d",&w[i],&c[i]);
for(int i=1;i<=n;i++) //逐个枚举每一件物品
	for(int j=1;j<=m;j++) // 枚举个个重量段的别抱
		if(j>=w[i]) //物品i要放入背包
			f[i][j]=max(f[i-1][j-w[i]]+c[i],f[i-1][j]);
		else	f[i][j]=f[i-1][j];
printf("%d\n",f[n][m]);
return 0;
}

题解bytaotao

0/1背包二维数组方法

Dev.C++动态规划01背包：背包是一种特殊动态规划，而01背包就是只有选与不选的状态，这是最简单的理解。

dp[i-1][j]:不选这件物品的情况。为什么是这样呢？j不动，是指没有放入任何东西。这就是不选的情况。

dp[i-1][j-v[i]]+w[i]:选择这件物品的情况。为什么呢？j-v[i]，是目前背包内剩余空间减去这件物品的体积，加w[i],是指加上这件物品的价值。

#include <bits/stdc++.h>
using namespace std;
int m,n,w[1001],c[1001];
//这里是二维数组版本来做0/1背包
int f[1001][1001];
//f[x][y]中，x是物品数量，y是重量。f[x][y]是指在数量为x，重量为y的情况下，最大价值

int main()
{
  cin>>m>>n;
  for(int i=1; i<=n; i++)
  {
    scanf("%d%d",&w[i],&c[i]);
    //输入重量和价值
  }
  for(int i=1; i<=n; i++)
  {
    for(int j=1; j<=m; j++)
    {
      //从重量和数量都为一开始枚举，之后不断累积
      if(j>=w[i]) //保证枚举的重量符合条件，不符合就不选，符合才选（所以叫0/1背包）
      {
        f[i][j]=max(f[i-1][j-w[i]]+c[i],f[i-1][j]);//符合的话还要从选和不选再选最大值
      }
      else
      {
        f[i][j]=f[i-1][j];//不符合直接不选，用上一组最大的即可
      }
    }
  }
  printf("%d\n\n\n\n\n\n\n\n\n",f[n][m]);//最后输出x=n,y=m的情况，也就是答案
  cout<<"你听懂了吗";
  return 0;
}