DP：zoj 2014 || poj 1384 Piggy-Bank（完全背包简单变形）

【转】http://blog.csdn.net/zxy_snow/article/details/6023963

?

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
using namespace std;
int main(void)
{
?int ncases,n;
?int suttle,pigweight,fullweight;
?int w[502],v[502],mmin[10001];
?cin >> ncases;
?while( ncases-- )
?{
??cin >> pigweight >> fullweight;
??suttle = fullweight - pigweight;
??cin >> n;
??for(int i=0; i<10001; i++)??? //装满的初始化
???mmin[i] = -10000000;
??mmin[0] = 0;???? //这个很重要
??for(int i=0; i<n; i++)
??{
???cin >> v[i] >> w[i];
???v[i] = -v[i];
??}
??for(int i=0; i<n; i++)
???for(int k=w[i]; k<=suttle; k++)
????mmin[k] = max( mmin[k-w[i]]+v[i],mmin[k] );
??if( mmin[suttle] == -10000000)
???cout << "This is impossible." << endl;
??else
???printf("The minimum amount of money in the piggy-bank is %d./n",-mmin[suttle]);
??}
return 0;
}