学步园

求装满背包价值最小。

这个是自己思考的哦~~哦也~

背包的方程那个是求最大的，然后我换成最小的，不对，一直不对，初始化也不对应该。

装满的看背包九讲那个，是要初始化成负无穷的，可是这么用min的话，不对。

然后我想到那啥了，最短路。

以前貌似遇到过求最长路，是把最短路的权值全部弄成负值，然后继续用普通最短路处理即可，最后再加个符号就OK了。

恍然大悟啊。。。这个可是我自己悟出来的，(*^__^*) 嘻嘻……把价值存成负值，然后算最大背包所能装满的重量即可。

求装满的时候，重量为0的包里面是0，其他都是负无穷，我用INT_MIN，后面判等的时候不对，索性自己写个数了。

PS： 还是用printf输出这种输出比较简便。。。

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