首页 > ACM题库 > HDU-杭电 > hdu 2660 Accepted Necklace-背包问题-[解题报告]C++
2014
02-12

hdu 2660 Accepted Necklace-背包问题-[解题报告]C++

Accepted Necklace

问题描述 :

I have N precious stones, and plan to use K of them to make a necklace for my mother, but she won’t accept a necklace which is too heavy. Given the value and the weight of each precious stone, please help me find out the most valuable necklace my mother will accept.

输入:

The first line of input is the number of cases.
For each case, the first line contains two integers N (N <= 20), the total number of stones, and K (K <= N), the exact number of stones to make a necklace.
Then N lines follow, each containing two integers: a (a<=1000), representing the value of each precious stone, and b (b<=1000), its weight.
The last line of each case contains an integer W, the maximum weight my mother will accept, W <= 1000.

输出:

The first line of input is the number of cases.
For each case, the first line contains two integers N (N <= 20), the total number of stones, and K (K <= N), the exact number of stones to make a necklace.
Then N lines follow, each containing two integers: a (a<=1000), representing the value of each precious stone, and b (b<=1000), its weight.
The last line of each case contains an integer W, the maximum weight my mother will accept, W <= 1000.

样例输入:

1 
2 1 
1 1 
1 1 
3 

样例输出:

1 

#include <stdio.h>
#include <string.h>
struct node {
    int v,w;

} a[21];
#define INF 0xfffffff
int f[1005][21];
int n, k,w;
void dp() {
    int i,j, p;
    int max;
    memset(f,0,sizeof(f));
    for(i=0; i<n; i++) {
        for(j=w; j>=a[i].w; j--) {
            for(p=1; p<=k; p++) {
                max = f[j][p];
                if(max<f[j-a[i].w][p-1]+a[i].v) max = f[j-a[i].w][p-1]+a[i].v;
                f[j][p] = max;
            }
        }

    }
    max =-INF;
    for(i=0; i<w; i++) if(max<f[i][k]) max = f[i][k];
    printf("%d\n",max);
}
int main() {
    int T,i;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&k);
        for(i=0; i<n; i++) scanf("%d%d",&a[i].v,&a[i].w);
        scanf("%d",&w);
        dp();
    }
    return 0;
}

解题转自:http://blog.csdn.net/yew1eb/article/details/9375941


  1. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环