背包问题动态规划

1006: 开心的Water

Time Limit: 1 Sec Memory Limit: 32 MB
Submit: 178 Solved: 62
[Submit][Status][Web Board]

Description

Water今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早Water就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为 j1，j2，……，jk，则所求的总和为：
v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）
请你帮助Water设计一个满足要求的购物单。

Input

多组数据。

每组数据的第1行，为两个正整数，用一个空格隔开：
N m
（其中N（<30000）表示总钱数，m（<25）为希望购买物品的个数。）
从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数
v p
（其中v表示该物品的价格(v<=10000)，p表示该物品的重要度(1~5)）

Output

每组输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）。

Sample Input

Sample Output

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
int max(int a, int b) {
    if (a > b)
        return a;
    return b;
}
int main() {
    int n, m;   
    while (scanf("%d%d", &n, &m)!= EOF) {
      int f[30001]; //记录背包放哪些物品能达到最大利用率 
      memset(f, 0, sizeof(int)*30001);
      int w[26];
      int v[26];
      memset(w, 0, sizeof(int)*26);
      memset(v, 0, sizeof(int)*26);
      int w_;
      int v_;
      int max_total = 0;
      for (int i = 1; i <= m; i++) {
        cin >> w_ >> v_;
        w[i] = w_;
        v[i] = v_;
      }
      
      //动态规划的自底向上解题 
      for (int i = 1; i <= m; i++) { //依次选择是否放物品1,2,3,4...m 
      	//对于每个物品，看背包是否能承载得了，以及为了达到背包的利用率最大化，需要考虑是否把该物品放入背包，同时记录下每考虑过一个物品后
		//背包的最大利用率 
        for (int j = n; j >=1; j--) {
            if (j - w[i] >= 0) {	//如果此时背包能够放物品i 
               f[j] = max(f[j], f[j-w[i]]+v[i]*w[i]);	//f[j]保持总价值不变，此时为放物品i, f[j-w[i]]+v[i]*w[i]此时放物品i,总价值为未放
			   											//物品i时的价值（查表获得，因为之前已经计算得到了）加上物品i的价值 
               max_total = max(max_total, f[j]); //用max_total来记录最后背包利用率 
            }
        }
      }
      cout << max_total << endl;
    }
    return 0;
}

 
/**************************************************************
    Problem: 1006
    User: 12330344
    Language: C++
    Result: Accepted
    Time:24 ms
    Memory:1316 kb

输出所选物品：

/*
 *记录了选择哪些物品使得背包的使用率
 *程序结束时，同时输出所选物品和背包的最大利用率 
 */
  
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
int max(int a, int b) {
    if (a > b)
        return a;
    return b;
}
int main() {
    int n, m;   
    while (scanf("%d%d", &n, &m)!= EOF) {
      int f[30001]; //记录背包放物品时的总价值，f[j]中j为载重 
      memset(f, 0, sizeof(int)*30001);
      int w[26]; //记录物品 
      int v[26]; //记录相应物品的价值
      
	  int selected_w[26]; //记录最终所选择的物品的载重 
	  int k = 0;
	  
      memset(w, 0, sizeof(int)*26);
      memset(v, 0, sizeof(int)*26);
      memset(selected_w, 0, sizeof(int)*26);
	   
      int w_;
      int v_;
      int max_total = 0;
      for (int i = 1; i <= m; i++) {
        cin >> w_ >> v_;
        w[i] = w_;
        v[i] = v_;
      }
      
      //动态规划的自底向上解题 
      for (int i = 1; i <= m; i++) { //依次选择是否放物品1,2,3,4...m 
      	//对于每个物品，看背包是否能承载得了，以及为了达到背包的利用率最大化，需要考虑是否把该物品放入背包，同时记录下每考虑过一个物品后
		//背包的最大利用率
		bool select = false; 
        for (int j = n; j >=1; j--) {
            if (j - w[i] >= 0) {	//如果此时背包能够放物品i 
               //f[j] = max(f[j], f[j-w[i]]+v[i]*w[i]);	//f[j]表示载重为j时，背包的总价值。f[j]保持总价值不变，此时为放物品i, f[j-w[i]]+v[i]*w[i]此时放物品i,总价值为未放
			   	
			  										//物品i时的价值（查表获得，因为之前已经计算得到了）加上物品i的价值 
			   if (f[j] < f[j-w[i]]+v[i]*w[i]) { //此时放物品i 
			   		f[j] = f[j-w[i]] + v[i]*w[i];
			   		select = true;//记录选择了物品i 
			   		
			   }
               max_total = max(max_total, f[j]); //用max_total来记录各种不同载重下，背包的最大总价值 
            }
        }
        if (select == true)
        	selected_w[k++] = w[i];
      }
      cout << max_total << endl;
      cout << endl;
      for (int i = 0; i < k; i++) {
      	 cout << selected_w[i] << endl;
      }
    }
    return 0;
}