1068 Find More Coins (30分)

Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she must pay the exact amount. Since she has as many as 104 coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find some coins to pay for it.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive numbers: N (≤104, the total number of coins) and M (≤102, the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the face values V1≤V2≤⋯≤V**k such that V1+V2+⋯+V**k=M. All the numbers must be separated by a space, and there must be no extra space at the end of the line. If such a solution is not unique, output the smallest sequence. If there is no solution, output "No Solution" instead.

Note: sequence {A[1], A[2], ...} is said to be "smaller" than sequence {B[1], B[2], ...} if there exists k≥1 such that A[i]=B[i] for all i<k, and A[k] < B[k].

Sample Input 1:

8 9
5 9 8 7 2 3 4 1

Sample Output 1:

1 3 5

Sample Input 2:

4 8
7 2 4 3

Sample Output 2:

No Solution

题目描述：商店有多种商品，给出多种商品的重量，而你的购物车有规定的称重量，不能超过规定的重量，现在要你求出在购物车刚好能够装满其重量时，能够装的最多件物品数。

输入：第一行n表示商品数，m表示购物车能够称的总重量。第二行为n个物品的重量。

输出：输出购物车总重量刚好等于m的商品的重量，递增输出。如果没有则输出No Solution。

因为题目要求递增输出，需要先给wet排个序。

解题思路：01背包问题。这道题中可以假设weight=value，dp可以用一维数组来维护。

01背包(思想)：有n种物品，每种物品只有一件，给出物品重量weight和价值value。

dp[ i ][ j ] 表示 在面对第 i 件物品，且背包容量为 j 时所能获得的最大价值

1. j < weight[ i ]，背包容纳不了第 i 件物品，dp[ i ][ j ] = dp[ i-1 ][ j ]

2. j >= weight[ i ]，背包可容纳第 i 件物品，可选放或不放，如果放入则dp[ i ][ j ] = dp[ i-1 ][ j - weight[ i ] ] + value[ i ]，如果不放入则与1)相同

转移方程：dp[ i ][ j ]=max{ dp [ i-1 ][ j ],dp[ i-1 ][ j-v[ i ]]+w[ i ]}

for i=1~N:
	for j=N~0:
		dp[j] = max{dp[j],dp[j-v[i]]+w[i]}

补充：

完全背包：有n种物品，每种物品有无数件，给出物品重量weight和价值value。

转移方程：dp[ i ][ v ] = max{ f [ i-1 ][ v - k*v[ i ]]+k*w[ i ] |0<=k*v[ i ]<=j}

for i=1~N:
	for j=0~N:
		dp[j] = max{dp[j],dp[j-v[i]]+w[i]}

提示：每种背包都是无限的。当我们把i从1到N循环时，dp[j]表示容量为j在前i种背包时所得的价值，这里我们要添加的不是前一个背包，而是当前背包。所以我们要考虑的是当前状态。

多重背包：有n种物品，每种物品给定了数量count，商品重量weight和价值value。

dp[ i ][ j ] = max{ dp[ i-1 ][ j- k* v[ i ]]+k*w[ i ] |0<=k<=n[ i ]}

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10086;
int wet[maxn];
int dp[maxn];
int vis[maxn][110];
int n, m;
bool cmp(int a, int b){
	return a > b;
}
int main()
{
	scanf("%d %d", &n, &m);
	memset(dp,0,sizeof(dp));
	memset(vis,false,sizeof(vis));
	for(int i=1; i<=n; i++) scanf("%d", &wet[i]);
	sort(wet+1,wet+n+1,cmp);
	for(int i=1; i<=n; i++){
		for(int j=m; j>=wet[i]; j--){//确保一定可放入第i件物品 
			if(dp[j-wet[i]]+wet[i]>=dp[j]){
				dp[j] = dp[j-wet[i]]+wet[i];
				vis[i][j] = true;
			}
		}
	}
	vector<int> ans;
	if(dp[m]!=m) printf("No Solution");
	else{
		int x = n, y = m;
		while(y>0){
			if(vis[x][y]){
				ans.push_back(wet[x]);
				y -= wet[x];
			}
			x--;
		}
		for(int i=0; i<ans.size(); i++){
			if(i) printf(" ");
			printf("%d", ans[i]);
		}
	}
	return 0;
}