背包问题/HDU串1248-白红宇

背包问题/HDU串1248

阅读量：4144 次

发布时间：2019-05-25

本文共 2442 字，大约阅读时间需要 8 分钟。

http://www.cnblogs.com/William-xh/p/7305877.html

真的是非常非常非常非常好的教程!

(一)小测试

https://blog.csdn.net/hpugym/article/details/43882781

这个题有点小别扭,就是把value和price反过来了

【代码片】

for (int i = 0; i < k; i++)

{//对于背包里的每个包,都要更新一下他们的状态吧= =-

//要明白这个包是自从下面往上面,然后是从右边往左边生成的,额可以

//别的其实你也是浪费了== - orx

for (int j = m; j <=price[i]; j--)

{//对于每一个i更新的一行啊....而且只要更新

//而且只要更新prcie[i]之后的就可以了,否则放不下去.

sum[j] = max(sum[j],sum[j - price[i]] + wight[i]);

//【是针对每个物品遍历的，所以里面是i啊，j只是那个状态而已i吧】

//啊,有点像是痕迹吧,虽然说是这样生成的,但是其实每次一行那样更新过去

//后面的就没意义了... 就是一行在始终动态更新着变化的

}

j-price[i],也只是坐标而已吧,(排除了123完全放不下的情况-那些就让其他的来填满吧-然后它的触角还是可以伸到123那些啊= -)

啊!for (int j = m; j <= price[i]; j--)

!!!只要遍历到这里就可以了,别的都是浪费的..

因为j更小的话根本装不下啊

但是1但是!这个等号嗷带着的，别忘了

【以及】从01背包往上面跑了一步,就是如果是一件的很多样物品,不如直接存贮一个cnt然后用k记录一下总数...方便快捷

(二)隐身(引申)

上次的小比赛有个题目是这个,再琢磨一遍吧

(代码有参考)

#include 
   
      #include 
    
       int w[3] = { 150,200,350 };//w[i]既是花费的代价，也是获得的价值  int dp[10005];//dp[i][j]表示在购买到i件物品,用j块钱所获得的最大价值.最后n-dp[3][n];  int max(int a, int b){	return a>b ? a : b;}int main(){	int T, i, j, n;	scanf_s("%d", &T);	while (T--)	{		scanf_s("%d", &n);		memset(dp, 0, sizeof(dp));		for (i = 0; i <= 2; i++)			for (j = w[i]; j <= n; j=j+10)				dp[j] = max(dp[j], dp[j - w[i]] + w[i]);		printf("%d\n", n - dp[n]);		//dp[N]J仅仅是存着的这个状态而已吧,然后记录的是数值,一样的		//= =	}	return 0;}

最后抽象出处理一件完全背包类物品的过程伪代码，以后会用到：

1 void CompletePack(int cost, int weight)

2 {

3 for (int v = cost; v <= V; v++)

4 f[v] = max(f[v], f[v - cost] + weight);

5 }

感觉这道题目用背包做是肯定不会错的..

【核心代码在这2行】

for (i = 0; i <= 2; i++)

for (j = w[i]; j <= n; j=j+10)

dp[j] = max(dp[j], dp[j - w[i]] + w[i]);

至于为什么...我隐隐约约的感觉,可能和顺序有关?