程序设计实习动态规划练习 Charm Bracelet(0/1背包问题dp)
总时间限制: 1000ms 内存限制: 65536kB
描述
Bessie has gone to the mall’s jewelry store and spies a charm bracelet. Of course, she’d like to fill it with the best charms possible from the N(1 ≤ N≤ 3,402) available charms. Each charm iin the supplied list has a weight Wi(1 ≤ Wi≤ 400), a ‘desirability’ factor Di(1 ≤ Di≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M(1 ≤ M≤ 12,880).
Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.
输入
Line 1: Two space-separated integers: N and M
Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di
输出
Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints
样例输入
4 6
1 4
2 6
3 12
2 7
样例输出
23
来源
USACO 2007 December Silver
这显然是一个0/1背包问题，考虑用dp解决。
用f[t]表示重量为t时候的最大价值，这个dp，之所以只需要一个维度，是有很好的扫描更新技巧保证的：
dp状态转移方程式为 f[t+w[i]]=max{f[t]+d[i],f[t+w[i]]}，对于每一个i，t从大到小扫描以避免一个物体被放入两次。
注意一下0/1背包和无限背包的小区别，如果从小到大扫描就变成了无限背包了，因为可以放入任意次。
背包问题思路大致如此，有很多变种，需要更高维度的dp，有些甚至需要一些技巧节省空间（维度太高可能MLE），有些需要利用单调性优化时间开销，例如单调队列，四边形不等式。虽然暂时我没有掌握，但是应该知道有这么一回事，做题时候绷紧dp的弦，思想正确就好了。
Accepted 256kB 170ms 373 B G++
#include<stdio.h>
int n,max_w,max_d;
int w[3403],d[3403];
int f[12881];
int main()
{
scanf("%d%d",&n,&max_w);
for (int i=1;i<=n;i++)
scanf("%d%d",&w[i],&d[i]);
for (int i=1;i<=n;i++)
for (int t=max_w-w[i];t>=0;t--)
if (f[t+w[i]]<f[t]+d[i])
f[t+w[i]]=f[t]+d[i];
for (int t=0;t<=max_w;t++)
if (f[t]>max_d)
max_d=f[t];
printf("%d\n",max_d);
return 0;
}