01背包

题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

• 0<N,V≤1000
• 0<vi,wi≤1000

题解：

首先这是思路：

1. 表示状态

   设f[i][j]表示只考虑前 i 个物品，总共体积为 j 时的最大价值。

2. 循环范围

   i 表示物品数量，物品最少 1 个，物品最多 n 个，因此 i 的循环范围是 1~n 。
   j 表示总共体积，体积最小是 0 ，体积最大是 V ，因此 j 的循环范围是 0~V 。

3. 状态转移

   由于每个状态是由前一个状态推来的，所以要决定当前物品是选还是不选。
   如果选这个物品不优，那么就不选它，所以每个状态一定不会比之前的任何一个状态更差。
   然后可以得出：

   如果不选当前物品，则价值为f[i-1][j]

   如果选当前物品：
   要给这个物品在 j 个单位的空间中腾出位置，还得保证留下的物品时最优的。
   留下的物品的总价值就存在f[i-1][j-v[i]]
   最后，还要加上选中物品的价值w[i]。
   综上所述，如果选当前物品，则价值为f[i-1][j-v[i]]+w[i]

   然后求出它们的较大值，存在f[i][j]
   现在可以列出转移方程：

   f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);

   有这样一个公理：只要每一步都是当前最优的，那结果一定是最优的。

有了这些，就可以打出code：

#include <bits/stdc++.h>
#define ll long long
#define N 1005
using namespace std;
inline ll read()
{
	ll x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=x*10+c-48;c=getchar();}
	return (f==1)?x:-x;
}//卡长
ll n=read(),V=read(),v[N],w[N],f[N][N];
int main()
{
	for(ll i=1;i<=n;i++) v[i]=read(),w[i]=read();
	for(ll i=1;i<=n;i++)
	{
	    for(ll j=0;j<=V;j++)
	    {
	        f[i][j]=f[i-1][j];
	        if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
	    }//判断j是否不小于v[i]，如果小于就肯定不能选当前物品，则f[i][j]=f[i-1][j]
	}
	cout << f[n][V];
	return 0;
}